一：前言
二叉树的遍历方法分四种:前序，中序，后序以及层次遍历。
其中，前中后遍历方法的实现分递归和非递归，非递归遍历的实现需要借助于栈。
实际上，递归的调用就是一种栈的实现，所以，非递归遍历就需要人工借助栈结构来实现。
而层次遍历需要借助队列。
二：前中后序遍历
递归遍历：
递归遍历的思想和方法很简单，通过调整输出语句来实现前，中，后三种遍历。
代码如下：
void show(BiTree T)
{
if(T)
{
printf("%c ",T->data);//修改这三个语句的顺序分别实现三种遍历
show(T->lchild);
show(T->rchild);
}
}
非递归遍历：
总结了5总不同的非递归遍历算法，四种思路，都需要借助栈来完成。
第一种遍历算法：
算法的思路：
1.从根结点开始，若当前结点的左孩子不为空，则遍历左孩子并进栈。
2.结点的左孩子为空时，出栈并遍历当前结点的右孩子结点
3.以右孩子结点为根结点，又沿着左孩子不断遍历，重复1.2步骤
此算法为前序遍历
void preorder1(BiTree T)//前序遍历1
{
LinkStack s;
InitStack(&s);
BiTree temp;
temp = T;
while(temp || !EmptyStack(s)) //第一个条件temp是为了进入循环
{
if(temp) //一直遍历左子树到底部
{
Push(&s,temp);
printf("%c",temp->data);
temp = temp->lchild;
}
else //lchild为空，跳转到rchild
{
Pop(&s,&temp);
temp = temp->rchild;
}
}
}
第二种遍历算法：
算法思路与第一种遍历算法一致，只是改变了遍历语句的位置，不是在进栈的时候输出，而是在出栈的时候输出，前序遍历则为中序遍历
1.从根结点开始，当前结点左孩子不为空时，左孩子进栈。
2.当前结点左孩子为空时，出栈并输出当前结点，然后跳转该结点的右孩子
3.重复1，2步骤直到栈空
void inorder(BiTree T)//中序遍历
{
LinkStack s;
InitStack(&s);
BiTree temp = T;
while(temp || !EmptyStack(s))
{
if(temp)
{
Push(&s,temp);
temp = temp->lchild;
}
else
{
Pop(&s,&temp);
printf("%c ",temp->data); //出栈时输出则为中序遍历
temp = temp->rchild;
}
}
}
第三种遍历算法：
此种算法为前序遍历
算法思路：1.先将根结点入栈
2.出栈栈顶并输出，先入栈当前结点的右孩子结点，在入栈当前结点的左孩子结点
3.重复第2步直到栈空
void preorder2(BiTree T)
{
LinkStack s;
InitStack(&s);
BiTree temp = T;
Push(&s,temp);
while(!EmptyStack(s))
{
Pop(&s,&temp); //出栈顶并输出
printf("%c ",temp->data);
if(temp->rchild) //入栈右孩子
{
Push(&s,temp->rchild);
}
if(temp->lchild) //入栈左孩子
{
Push(&s,temp->lchild);
}
}
}
第四种遍历算法：
后序遍历的非递归实现比较复杂，要保证输出当前结点时左右孩子结点已经输出（或者左右孩子为空）
即每输出一个结点要满足以下两个条件之一：
1.此结点的左右孩子为空
2.此结点的左右孩子已经遍历
算法思路：1.先将根结点入栈，以栈空为循环停止的条件
2. 用结点指针pre记录上一个输出结点地址，cur记录当前结点地址
2.1 当前结点的左右孩子为空时，或者pre记录的结点为当前结点的左（右）孩子时，出栈并输出当前结点，并更新pre
2.2 否则按照右孩子，左孩子的顺序入栈
3.循环第2步直到栈空