文档介绍：一、设计思想
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 tree * rchild;
unsigned int isOut; //专为后序遍历设置的,0为不需要被输出,1为需要被输出
}TreeNode, *