常见遍历方式有四种，先序、中序、后序、层次遍历。
1. 先中后序遍历（递归）
void preOrder(tree t)
{
if(t != NULL)
{
visit(t);
preOrder(t->lchild);
preOrder(t->rchild);
}
}
先中后，不过是调整了visit的顺序而已。
2. 先中序遍历（非递归）
void InOrder2(tree t)
{
InitStack(s);
tree p = t;
while(!p || !IsEmpty(s))
{
if(p)
{
push(s,p);
p = p->lchild;
}
else
{
pop(s,p);
visit(p);
p = p->rchlid;
}
}
}
无论前序还是中序，结点指针的顺序都是
- 指向根结点，入栈
- 不断指向左孩子，入栈（此时访问结点，前序）
- 直到为空
- 指向通过出栈结点，指向双亲（此时访问结点，中序）
- 指向右孩子
不断重复上述过程，
直到指向二叉树右子树最下层的最右的结点，此时由于不用指向双亲，因此临时保存双亲结点的栈已经为空。
再指向这个结点的右孩子（栈依旧为空），其右孩子也为空，因此满足退出循环。
从微观角度来看
指针指向一个结点
如果要访问其左孩子（左孩子不为空时就要访问），则要保存该结点（入栈）
以备指针指向该结点（出栈），以访问其右孩子
每一个分支，都要先指向双亲结点，
然后指向它的左孩子（也许要遍历左子树），
然后回头指向双亲结点，
接着指向它的右孩子（也许要遍历右子树）
前序，中序的区别在于
前序是第一次指向结点时，访问结点
中序是指针指向结点的左孩子，通过出栈，指针重新指向结点时，访问结点
3. 后序非递归
后序遍历方式依旧使用栈，分析可得遍历流程为：
I. 指针指向根结点，找到其左孩子
II. 指针指向其左孩子，访问左子树
III. 指针指向其右孩子，访问右子树
IV. 指针指向结点，访问
V. 指针指向其双亲结点
入栈规则：结点入栈，左子树入栈，所有左子树出栈后，结点右子树进栈。
出栈规则：结点为叶子节点，立即出栈；结点的左右孩子均被访问过。
一个子树的根结点在这个过程中总共被指针指向过三次，第一次通过其访问其左孩子，第二次通过其访问其右孩子，最后一次访问该结点。
如何判断是第几次指向结点以确定该如何操作是问题关键。
方法有两种：
(1) 保留指向上一次出栈结点的指针
若其等于栈顶结点的左孩子，则表明左子树遍历完成，开始遍历右子树
若其等于栈顶结点的右孩子，则表明现结点的左右子树都遍历完毕，可以出栈
如果都不是，指针指向栈顶左孩子，并入栈
(2) 创建一个tag栈，记录s栈中结点被访问的次数，每次只处理栈顶结点。
根结点入栈，tag为0，则开始遍历左子树，且tag++
tag为1，则开始遍历右子树，且tag++
tag为2，则代表已经遍历完左右子树，将结点，以及tag出栈
void traverse(tree t)
{
initStack(s);
initStack(tag);
tree p = t;
push(p,s);
push(0,tag);
while(!IsEmpty(s))
{
switch(tag[top])
{
case 0:
{
tag[top]++;
p = getTop(s)->lchild;
if(p)
{
push(p,s);
push(0,tag);
}
}
case 1:
{
tag[top]++;
p = getTop(s)->rchild;
if(p)
{
push(p,s);
push(0,tag);
}
}
case 2:
{
visit(s[top]);
pop(s);
pop(tag);
}
}
}
}
(3) 双栈法
- 根结点进入s1
- 根结点出栈，进入s2
- 根结点的左结点进入s1，右结点进入s1
- 右结点出栈，进入s2
- 左结点出栈，进入s2
因此，进入s2的顺序是，根结点，右结点，左结点
出栈的顺序，左结点，右结点，根结点
void PostTraverse(BiTree T){
BiTree root = T ;
SqStack S1,S2; //辅助栈，S1用来存储树入栈，S2用来存储后序遍历序列
//初始化
InitStack(S1);
InitStack(S2) ;
Push(S1,root); //1.首先根节点入栈
while(!isEmpty(S1)){ //当栈S1不为空时：1.先S1出栈 2.将从S1出栈的栈顶元素入栈S2
BiTree P=Pop(S1);
Push(S2,P);
if(P->lchild !=NULL) Push(S1,P->lchild);
if(P->rchild !=NULL) Push(S1,P->rchild) ;
}
while(!isEmpty(S2)){
printf("%c",(*(--S2.top))->data);
}
}
