二叉树02.深度优先遍历之Morris遍历
发布网友
发布时间：2024-09-27 00:50
共1个回答
热心网友
时间：7分钟前
前一篇文章介绍了深度优先遍历的递归实现和迭代实现，这两种方式的时间复杂度都是O(n)，空间复杂度都是O(h)，本文将要介绍的 Morris 遍历的时间复杂度依然为O(n)，但空间复杂度仅为O(1)，其中 n 为节点数，h 为树的高度。
算法来历
1968年，《计算机程序设计艺术》的作者 Knuth 提出了一个问题：设计一个无需堆栈和额外标志域的非递归的中序遍历算法，且当遍历结束时树结构不变。此后，诞生了许多解决方案，而Morris 遍历是其中最优雅的一种（见参考资料[1]）。
此算法由 Joseph M. MORRIS 在1979年的论文 "Traversing Binary Trees Simply and Cheaply"[2] 中首次提出。顺便再说一句，这个 MORRIS 正是大名鼎鼎的 KMP 算法的作者之一。
代码仓库： github.com/patricklaux/... 系列文章 (1) 深度优先遍历之递归和非递归遍历 (2) 深度优先遍历之 Morris 遍 历 【本文】 (3) 一种无需队列的层序遍历算法 IDDFS (4) 深度分析AVL树的实现与优化 (5) B树详解与实现
如果了解线索二叉树的话，肯定对前驱和后继非常熟悉。 通过在二叉树节点增加前驱和后继指针，可以非常方便地进行向前查找、向后查找和遍历等线性化操作，相当于是二叉树和链表的结合。这其中指向前驱和后继的指针称之为线索，而包含线索的二叉树则称之为线索二叉树(Threaded Binary Tree)[3]。 譬如 Java 的 HashMap 中的 红黑树节点，就增加了 prev 和 next 指针，其节点结构类似如下：
这种方式需要额外内存来保存前驱和后继指针，那么是不是有一些其它方式来避免这个问题呢？ 对于二叉树，如果 n 为节点数，那么会有 2n 个链接，其中有 n+1 个空链接。那么，一个朴素的想法是使用节点的空链接来保存前驱和后继。
如上图所示，空的右孩子指针指向其后继节点（红色线），就可以用 node.right 来遍历了。
特别注意：Morris 遍历算法的后继指针是在遍历过程中动态建立和删除的。
另外，能够利用空的右孩子来保存后继指针，这其实隐含了一个假设： 如果一棵二叉搜索树中的一个节点有两个孩子（非空，如 d, b, f），那么它的前驱没有右孩子，它的后继没有左孩子。 好吧，这其实是《算法导论》中的一道证明题，根据二叉搜索树左小右大的基本性质，即可证明此假设成立，证明过程就不展开了。
既然高老爷子的问题是关于中序遍历的，那么就先从中序遍历开始吧。
过程描述：
核心思路：
代码实现：
先序遍历的代码几乎与中序遍历完全一致，区别仅在于何时访问值。
后序遍历还是最复杂的。
如前文所述，后序遍历需要先访问右子树，再访问当前节点。但由于Morris遍历没有栈，所以无法通过再次入栈来调换访问顺序。
我们再观察下上面的左图，会发现只要将节点反转后访问即是后序遍历。
结束，正好是：a, c, b, e, g, f, d。
Morris 遍历在原论文中仅指中序遍历，为什么之后推广到先序遍历和后序遍历，我没有找到相关资料。 推广到先序遍历还不错，但推广到后序遍历就一点都不优雅了，太丑陋！！！
Morris 遍历算法是优点和缺点都非常明显的一个算法。 优点：无需使用额外的栈空间，空间复杂度为O(1)。 缺点：遍历过程中改变了树结构，一次遍历完成之前不能开始另一次遍历。
另，参考资料 1 证明了 Morris 遍历其实与递归遍历一样，同样隐式使用了栈（如图2所示的红色线条），这个栈最大时等于树高（如图2所示最多时会有2条红色线），因此其与显式使用栈的遍历是可以等价转换的。
Morris 遍历虽然隐式使用了栈，但并没有使用额外的栈空间，所以其空间复杂度依然是O(1)。 下篇文章将聊一聊层序遍历，重点是介绍非常优秀的 IDDFS 算法，欢迎继续阅读！谢谢！
PS：有根有据有态度的分享，如果觉得不错，记得点赞关注哦！
参考资料
[1] MATETI, MANGHIRMALANI. MORRIS TREE TRAVERSAL ALGORITHM RECONSIDERED[J]. SCI COMPUT PROGRAM, 1988.
[2] Morris J M . Traversing Binary Trees Simply and Cheaply[J]. Information Processing Letters, 1979, 9(5):197-200.
[3] 严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 清华大学出版社, 2007.
