莫里斯遍历

定义

莫里斯遍历是二叉树的一种遍历算法，它在中序遍历中可以不用递归、也不用栈，只用常数个额外变量完成遍历^[1]。通常的递归写法要占用与树高成正比的调用栈空间，用栈模拟的迭代写法同样要 O(h) 的辅助空间；莫里斯遍历把额外空间压到 O(1)^[2]。

它的做法是对线索二叉树思想的变通：遍历期间临时把节点的空右指针当作线索指向中序后继，借这些临时链接回到上层，访问完再把指针复原成原样^[3]。除中序外，这一思路也可用于前序遍历^[4]。

原理

中序遍历要求先走完左子树、再访问根、最后进入右子树。用递归或栈的算法靠外部结构记录这条返回路径，莫里斯遍历则把返回信息直接写进树里：对每个有左孩子的节点 curr，先在它的左子树中一路向右走到最右下节点，也就是 curr 的直接前驱^[5]。

若该前驱的右指针为空，说明是第一次到达 curr，就把前驱的右指针指向 curr 作为临时线索，然后向左下行进入左子树^[6]。若该前驱的右指针已经指向 curr，说明左子树已经访问完毕，此时把这条线索断开、恢复成空指针，再访问 curr，然后转向右孩子^[7]。若 curr 本身没有左孩子，直接访问它并转向右孩子，循环直到 curr 为空^[4]。

查找前驱的内层循环需要写成「右指针非空且不等于 curr」两个条件并列。如果只判断右指针非空，走到线索处会顺着已建立的线索回到 curr，再从 curr 向右下行，循环无法结束^[8]。此外，断开线索与访问节点这两步的顺序会影响中间状态的树形：先执行 pred.right = NULL 再输出当前节点，能保证每次迭代之间的树结构与原树一致^[8]。

每一条线索都只被建立一次、拆除一次，因此内层寻找前驱的循环虽然嵌套在外层循环里，总体代价仍是线性的，时间复杂度为 O(n)，额外空间为 O(1)^[1]。

发展历程

1968 年，高德纳提出一个问题：是否存在既不使用栈、也不使用标记位、又不用递归，并且遍历结束后树保持原状的二叉树中序遍历算法^[9]。此后文献中陆续出现多种解法，其中 1979 年 J. M. Morris 在《Information Processing Letters》上发表的算法被认为是较为简洁的一种^[9]。

1988 年，Prabhaker Mateti 与 Ravi Manghirmalani 给出对该算法的推演式分析，指出它实际上仍然存在一个「栈」，只不过这个栈占用了树节点原本空闲的右指针域，与树的存储空间分时复用^[10]。1986 年 T. I. Fenner 与 G. Loizou 的工作则从带栈的遍历算法出发推导出同一算法，并说明它可由线索二叉树遍历变形得到^[11]。

应用

莫里斯遍历适合内存受限、或需要把空间开销压到最低的场合，也常用于避免深树递归导致的栈溢出^[12]。在算法练习中，它常被用来解二叉搜索树的中序相关问题，例如求第 k 小的元素，因为二叉搜索树的中序序列本身即为升序^[13]。

在需要逐步给出中序元素的场景中，可以用莫里斯遍历实现二叉搜索树迭代器：把遍历状态保存在一个当前指针里，每次取下一个元素时完成一次线索建立或拆除，单次操作摊还代价为常数，额外空间为常数，优于常见的 O(h) 栈式实现^[2]。

在只允许读访问的环境中情况不同。若数据位于只读存储器，或同一份数据被多个处理器同时访问，遍历过程中修改指针的做法就不适用，这类场景下需要另行设计不修改指针的方案^[14]。

局限

莫里斯遍历要在遍历途中改动树本身，虽然结束时恢复原状，但整个过程中树都处于被修改的状态。这与只读访问的约束冲突，在只读存储器或多处理器共享同一数据结构的情况下无法直接使用^[14]。

若在遍历中途提前返回（例如找到目标元素就跳出），已建立的线索不会被拆除，树的结构会残留临时指针，后续访问可能出错，因此实现上通常需要把结果先保存下来、走完全程再返回^[13]。

该算法容易扩展到前序与逆序（在二叉搜索树上从大到小）遍历，后序则困难得多。把前序的访问时机简单反向并不能得到后序，得到的是「根—右—左」的逆前序；要真正做到 O(1) 空间的后序遍历，需要在退出每棵左子树后就地反转一段右指针路径，即所谓反转主干的做法，实现复杂度更高^[8]。

与递归写法相比，莫里斯遍历的代码更难写对，常数因子也偏大，需要额外的指针操作^[12]。

参见

• 二叉树 —— 莫里斯遍历所作用的数据结构。

• 线索二叉树 —— 莫里斯遍历借用的核心思想来源。

• 二叉搜索树 —— 其迭代器等场景常用莫里斯遍历实现常数空间遍历。

• 深度优先搜索 —— 树与图遍历所属的更大类算法。