遍历(非递归)

• 先序遍历算法

1. 首先申请一个新的栈，记为stack；
2. 然后将头结点head压入栈stack中；
3. 每次从stack中弹出栈顶节点，记为cur，然后打印cur节点的值。如果cur右孩子不为空的话，将cur的右孩子压入stack中。最后如果cur的左孩子不为空的话，将cur的左孩子压入stack中。
4. 不断重复步骤3，直到stack为空，全部过程结束。

• 中序遍历算法

1. 申请一个新的栈，记为stack，申请一个变量cur，初始时令cur等于头结点；
2. 先把cur节点压入栈中，对以cur节点为头的整颗子树来说，依次把整颗树的左边界压入栈中，即不断令cur==cur.left，然后重复步骤2；
3. 不断重复步骤2，直到发现cur为空，此时从stack中弹出一个节点，记为node。打印node的值，并让cur==node.right，然后继续重复步骤2；
4. 当stack为空并且cur为空时，整个过程结束。

• 后序遍历算法

方法一：使用两个栈实现

1. 申请一个栈，记为s1，然后将头节点压入s1中；
2. 从s1中弹出的节点记为cur，然后先把cur的左孩子压入s1中，然后把cur1的右孩子压入s1中；
3. 在整个过程中，每一个从s1中弹出的节点都放进第二个栈s2中；
4. 不断重复步骤2和步骤3，直到s1为空，过程停止。
5. 从s2中依次弹出节点并打印，打印的顺序就是后续遍历的顺序了。

方法二：使用一个栈实现

1. 申请一个栈，记为stack，将头节点压入stack，同时设置两个变量h和c。在整个流程中，h代表最近一次弹出并打印的节点，c代表当前stack的栈顶节点，初始时令h为头节点，c为NULL；
2. 每次令c等于当前stack的栈顶节点，但是不从stack中弹出节点，此时分以下三种情况：
   (1)如果c的左孩子不为空，并且h不等于c的左孩子，也不等于c的右孩子，则把c的左孩子压入stack中；
   (2)如果情况1不成立，并且c的右孩子不为空，并且h不等于c的右孩子，则把c的右孩子压入stack中；
   (3)如果情况1和情况2都不成立，那么从stack中弹出c并打印，然后令h等于c。
3. 一直重复步骤2，直到stack为空，过程停止。