void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d\n", BT->Data);
}
}
后序遍历的非递归实现
思路一：
对于一个节点而言，要实现访问顺序为左儿子-右儿子-根节点，可以利用后进先出的栈，在节点不为空的前提下，依次将根节点，右儿子，左儿子压栈。故我们需要按照根节点-右儿子-左儿子的顺序遍历树，而我们已经知道先序遍历的顺序是根节点-左儿子-右儿子，故只需将先序遍历的左右调换并把访问方式打印改为压入另一个栈即可。最后一起打印栈中的元素。代码如下：
void PostOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S1 = CreatStack(MAX_SIZE); //创建并初始化堆栈S1
Stack S2 = CreatStack(MAX_SIZE); //创建并初始化堆栈S2
while(T || !IsEmpty(S1))
{
while(T) //一直向右并将沿途节点访问（压入S2）后压入堆栈S1
{
Push(S2, T);
Push(S1, T);
T = T->Right;
}
if (!IsEmpty(S1))
{
T = Pop(S1); //节点弹出堆栈
T = T->Left; //转向左子树
}
}
while(!IsEmpty(S2)) //访问（打印）S2中元素
{
T = Pop(S2);
printf("%d\n", T->Data);
}
}
思路一的优点是由于利用了先序遍历的思想，代码较简洁，思路较清晰。缺点是需要用一个栈来存储树的所有节点，空间占用较大。
思路二：
要访问一个节点的条件上一个访问的节点是右儿子。我们可以增加一个变量Prev来判断当前节点Curr的上一个节点与它的关系来执行相应的操作。
• 若Prev为空(Curr节点是根节点)或者Prev是Curr的父节点，将Curr节点的左孩子和右孩子分别压入栈；
• 若Prev是Curr的左儿子，则将Curr的右儿子压入栈；
• 否则Prev是Curr的右儿子，访问Curr;
代码如下:
void PostOrderTraversal(BinTree BT)
{
if(BT == NULL)
return ;
Stack S = CreatStack(MAX_SIZE);
BinTree Prev = NULL , Curr = NULL; //初始化
s.push(BT);
while(!IsEmpty(S))
{
Curr = Top(S); //将栈顶元素赋给Curr
if(Prev == NULL || Prev->Left == Curr || Prev->Right == Curr) //若Prev为NULL或是Curr的父节点
{
if(Curr->Left != NULL)
Push(S, Curr->Left);
else if(Curr->Right != NULL)
Push(S, Curr->Right);
}
else if(Curr->Left == Prev) //若Prev是Curr的左儿子
{
if(Curr->Right != NULL)
Push(S, Curr->Right);
}
else
{
printf("%d\n", Curr->Data); //访问当前节点
Pop(S); //访问后弹出
}
Prev = Curr; //处理完当前节点后将Curr节点变为Prev节点
}
}
4. 层序遍历
二叉树遍历的核心问题是二维结构的线性化。我们通过节点访问其左右儿子时，存在的问题是访问左儿子后，右儿子怎么访问。因此我们需要一个存储结构保存暂时不访问的节点。前面三种遍历方式的非递归实现，我们是通过堆栈来保存。事实上也可以通过队列来保存。