递归非递归两种算法遍历二叉树.doc

一、设计思想
1. 用递归算法遍历 
设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历 
前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。 
中序遍历： 先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。 
后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。 
2. 用非递归算法遍历 
设计思想：主要是通过栈的存取，判空，从而实现树的遍历 
前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。 
中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈元素为0。
 
后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。重复循环操作，直到栈没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。
开始
Root=null
Y
N
输出数据
=null
Root=Tree t
=null
N
Y
Y
N
结束
开始
Root=Tree t
Root=null
=null
N
N
输出数据
Y
=null
结束
Y
N
开始
Root=Tree t
Root=null
=null
=null
Y
输出数据
结束
Y
Y
Y
N
N
N
二、算法流程图
图1 递归算法-先序遍历 图2 递归算法-后序遍历 图3 递归算法-中序遍历
开始
=
null
Tree t=root
output
t = null
N
Y
Push
=
null
Push
N
Y
N
栈为空
t=
()
Y
N
结束
Y
开始
Tree t=root
压栈
t = null
N
Y
t=current.
getLtree()
t=
()
output
t=current.
getRltree()
栈为空
N
结束
Y
图4 非递归算法-先序遍历 图5 非递归算法-中序遍历
开始
Tree t=root
Push
t = null
N
Y
t=()
标签栈压栈
t=
()
标签栈出栈
赋值给标志位
判断栈是否已经入栈过
N
Y
t=()
标签栈压栈
出栈并赋值t
Output
Current=null
树栈为空且当前节点为空
N
结束
Y
图6 非递归算法-后序遍历
三、源代码
#include<>
#include<>

typedef char ElemType;
//定义树结构
typedef struct tree
{
ElemType data;
struct tree * lchild;
struct tr