遍历(非递归)
-
先序遍历算法
- 首先申请一个新的栈，记为stack；
- 然后将头结点head压入栈stack中；
- 每次从stack中弹出栈顶节点，记为cur，然后打印cur节点的值。如果cur右孩子不为空的话，将cur的右孩子压入stack中。最后如果cur的左孩子不为空的话，将cur的左孩子压入stack中。
- 不断重复步骤3，直到stack为空，全部过程结束。
-
中序遍历算法
- 申请一个新的栈，记为stack，申请一个变量cur，初始时令cur等于头结点；
- 先把cur节点压入栈中，对以cur节点为头的整颗子树来说，依次把整颗树的左边界压入栈中，即不断令cur==cur.left，然后重复步骤2；
- 不断重复步骤2，直到发现cur为空，此时从stack中弹出一个节点，记为node。打印node的值，并让cur==node.right，然后继续重复步骤2；
- 当stack为空并且cur为空时，整个过程结束。
-
后序遍历算法
方法一：使用两个栈实现
- 申请一个栈，记为s1，然后将头节点压入s1中；
- 从s1中弹出的节点记为cur，然后先把cur的左孩子压入s1中，然后把cur1的右孩子压入s1中；
- 在整个过程中，每一个从s1中弹出的节点都放进第二个栈s2中；
- 不断重复步骤2和步骤3，直到s1为空，过程停止。
- 从s2中依次弹出节点并打印，打印的顺序就是后续遍历的顺序了。
方法二：使用一个栈实现
- 申请一个栈，记为stack，将头节点压入stack，同时设置两个变量h和c。在整个流程中，h代表最近一次弹出并打印的节点，c代表当前stack的栈顶节点，初始时令h为头节点，c为NULL；
- 每次令c等于当前stack的栈顶节点，但是不从stack中弹出节点，此时分以下三种情况：
(1)如果c的左孩子不为空，并且h不等于c的左孩子，也不等于c的右孩子，则把c的左孩子压入stack中；
(2)如果情况1不成立，并且c的右孩子不为空，并且h不等于c的右孩子，则把c的右孩子压入stack中；
(3)如果情况1和情况2都不成立，那么从stack中弹出c并打印，然后令h等于c。 - 一直重复步骤2，直到stack为空，过程停止。
