二叉树的迭代遍历

二叉树的迭代遍历

递归形式的遍历是显然的，怎么不依赖递归实现遍历？

前序遍历

用一个栈存储右子节点，访问左子节点，直至没有左孩子。每次从栈中取出一个节点。 均摊时间复杂度和空间复杂度均为 $O(n)$。 空间复杂度的常系数比递归更小。

中序遍历

先遍历左节点，并用辅助栈存储，直至没有左子节点，取出栈顶节点并访问，然后转向该节点的右子节点。

正确性：数学归纳

假设算法可正确遍历规模不超过 $n$ 的二叉树，考察任一规模为 $n+1$ 的二叉树， 设根为 $x$，藤的终点为 $t$，$t$ 的右孩子为 $y$。 算法经历了四个阶段：

• 遍历藤
• 访问 $t$
• 中序遍历 $y$ 子树
• 完成删去 $t$ 后的 $x$ 子树的中序遍历 其中 $y$ 子树和删去 $t$ 子树后的 $x$ 子树规模必然小于等于 $n$

直接后继/前驱

直接后继：指中序遍历中遍历该节点后下一个节点。 两种情况：

• 若有右子树，则直接后继为右子树的最左儿子
• 若没有右子树，则直接后继为最高右父亲的左父亲。
• 性能：$O(n)$

后序遍历

先遍历左子节点，若有右子节点，优先入栈，若有左子节点，入栈并转向左子节点，否则转向右子节点

层次遍历

广度优先，每次左孩子先入队，右孩子后入队。 时间和空间复杂度均为 $O(n)$

重建

先序、中序、后序、层次遍历都无法单独重建出一棵二叉树。

先序（后序）+中序

采用分治的方法。

• 对于先序遍历的首元素，即树的根 x，在中序遍历中找到 x
• 则中序遍历中的前缀即为左子树的遍历，后缀即为右子树的遍历，则也可以确定先序遍历中的左右子树的遍历
• 可以再对左右子树进行重建 $O(n)$ 时间完成重建

先序+后序+真二叉树

若树不是真二叉树，对于只有一个孩子的节点，无法确定是左孩子还是右孩子。 若约定二叉树为真二叉树（每个节点或有两个孩子或没有孩子），则先序+后序遍历也可重建出唯一的二叉树。 先分别通过先序和后序遍历序列找到 $l$ 和 $r$ 的秩，接着在后序遍历序列中搜索 $l$，即可确定左子树的先后序遍历序列，同理可确定右子树的先后序遍历序列。 $O(n)$ 时间可完成重建

增强序列

在遍历过程中遇到的空节点标记为^，则先序或后序遍历可以单独重建出二叉树，但中序遍历不可以。