二叉树的非递归遍历运用到堆栈
中序遍历
循环的思路是
- 遇到一个节点，就把它压栈，并去遍历它的左子树。
- 当左子树遍历结束之后，从栈顶弹出这个节点并访问它。
- 然后按其右指针再去按中序的遍历循环去遍历该节点的右子树。
代码实现
void InOrderTraversal(BinTree BT) { BinTree T = BT; Stack S = CreatStack(); //创建并初始化堆栈S while (T || !IsEmpty(S)) //节点和栈都为空时才停止循环 { while (T) //一直向左并将沿途节点压入堆栈 { Push(S, T); T = T->Left; } if (!IsEmpty(S)) //当遇到左子树为空时，进行出栈 { T = Pop(S); //弹出栈顶元素 printf("%5d", T->data); //访问栈顶元素 T = T->Right; //转向右子树 } } }
思路图解
从中序非递归遍历的代码上，可以将压栈时看做是第一次经过节点，将出栈是看做是第二次经过节点。所以结合之前学的递归遍历， 中序的非递归遍历代码中，才会在出栈时（即第二次经过节点时）访问节点。
所以要写出先序的非递归遍历就比较简单了：
先序遍历
将访问放在第一次经过节点时，就变成了先序的非递归遍历代码了。
代码实现
void PreOrderTrversal(BinTree BT) { BinTree T = BT; Stack S = CreatStack(); //创建并初始化堆栈S while (T || !IsEmpty(S)) //节点和栈都为空时才停止循环 { while (T) //一直向左并将沿途节点压入堆栈 { Push(S, T); printf("%5d", T->data); //访问栈顶元素 T = T->Left; } if (!IsEmpty(S)) //当遇到左子树为空时，进行出栈 { T = Pop(S); //弹出栈顶元素 T = T->Right; //转向右子树 } } }
再看后序的非递归遍历，似乎上面的代码中只有第一次经过和第二次经过，没有第三次经过节点的了，所以不能在原来的基础上调整代码来实现后序非递归遍历了。
后序遍历
要实现后序非递归遍历，可以借助两个堆栈，一个用于存储遍历的序列，另一个用于存储中间节点。
具体实现的思路：
- 初始化两个堆栈s1和s2，将根节点压入s1中。
- 从s1中弹出栈顶节点，将其压入s2中。
- 如果该节点有左子节点，则将左子节点压入s1中。
- 如果该节点有右子节点，则将右子节点压入s1中。
- 重复步骤2到步骤4，直到s1为空。
- 从s2中依次弹出节点并输出，即可得到后序遍历序列。
思路图解
end
