二叉树非递归遍历实现代码（深度遍历）

栈的先进后出特性

也就说 一次次的保护现场操作所保存下来的内容，被压入一个栈中。
而恢复现场，恰好是把原来保存栈中的那些内容，挨个弹出，恢复保存的状态。

实现递归函数 其中有个非常重要的角色 - 栈
当你使用递归函数的时候，这个栈 你是看不到的，是系统栈，系统默默做了这些事情。

总结：
首先从根节点开始，入栈一个节点，然后不停重复一下操作：

如果栈不空，就出栈一个元素，并对其访问，之后再检测其左、右孩子是否为空，如果为空，则不需要其左、右孩子入栈，否则需要入栈，注意入栈顺序，右孩子先入栈，左孩子后入栈。
如果栈为空，说明 整个遍历结束
这就是借助我们自己设定的栈 实现先序遍历的方法。

preorder
vt. 预订
n. 前序

recursion
n. [数] 递归，循环；递归式

出栈是在循环内，在栈空判断之后执行的，
哪怕此时因为出栈 导致栈空，循环的判断已经结束了，暂时不会判断，
并且下面紧跟着入栈操作。

所以即便中间栈空，循环也不会断掉，除非此时栈空 且后面没有左右孩子可以入栈，才会导致循环结束。此时恰好 遍历完成。

逆后序 是把逆序倒过来。
先序遍历 ：先遍历根结点，然后遍历左子树，再遍历右子树
后序遍历 ：先遍历左子树 ，然后遍历右子树，再遍历根结点
逆后序遍历 ：先遍历根结点，然后遍历右子树，再遍历左子树

先序遍历 和 逆后序遍历 区别：仅仅在 左右子树 的遍历顺序不同。

交换 左右子树 遍历顺序

最后把逆后序遍历序列 逆过来：
外加一个辅助栈，把逆后序遍历序列 压入栈中 ，再逐个出栈 ，就得到后序遍历序列。

postorder
n. [计] 后根次序；后缀次序

从根节点开始，沿着左孩子指针 ，一直往左走，直到遇到左孩子指针为空的节点，把所途径的节点全部入栈， 然后出栈一个节点，并访问这个节点，然后检测其右孩子是否存在，存在则取其右孩子入栈，从其右孩子开始，重复之前的过程，一直往左走，并把途径的节点全部入栈，直到来到左孩子为空的节点，出栈节点并访问，取其右孩子。。。（做重复的事情）；不存在则继续出栈。

从根节点开始，一直往左走，途径节点全部入栈，直到左节点为空，出栈一个，先往右走一步，再一直往左走。。。

inorder
n. 中根次序

外层循环条件的条件 ：栈不空 或者 p不空 即 top != -1 || p!= NULL

如果栈不空的时候，出栈一个元素，若恰好导致栈空，
此时栈空，p往右走一步，恰好出栈元素的右孩子不空，还有节点需要遍历。
若此时回到主循环条件那里，如果仅对 栈空 进行判断的话，此时就该跳出循环，剩下节点无法遍历，因此定上 p不空的判断条件。