深度优先

1. 概述 前一篇文章介绍了深度优先遍历的递归实现和迭代实现，这两种方式的时间复杂度都是 \( O(n) \)，空间复杂度都是 \( O(h) \)，本文将要介绍的 Morris 遍历的时间复杂度依然为 \( O(n) \)，但空间复杂度仅为 \( O(1) \)，其中 n 为节点数，h 为树的高度。 算法来历 1968年，《计算机程序设计艺术》的作者 Knuth 提出了一个问题：设计一个无需堆栈和额外标志域的非递归的中序遍历算法，且当遍历结束时树结构不变。此后，诞生了许多解决方案，而Morris 遍历是其中最优雅的一种（见参考资料1）1。 此算法由 Joseph M. MORRIS 在1979年的论文 “Traversing Binary Trees Simply and Cheaply2” 中首次提出。顺便再说一句，这个 MORRIS 正是大名鼎鼎的 KMP 算法的作者之一。 代码仓库：https://github.com/patricklaux/perfect-code 2. 算法解析 线索二叉树 如果了解线索二叉树的话，肯定对前驱和后继非常熟悉。 通过在二叉树节点增加前驱和后继指针，可以非常方便地进行向前查找、向后查找和遍历等线性化操作，相当于是二叉树和链表的结合。这其中指向前驱和后继的指针称之为线索，而包含线索的二叉树则称之为线索二叉树(Threaded Binary Tree)3。 譬如 Java 的 HashMap 中的 红黑树节点，就增加了 prev 和 next 指针，其节点结构类似如下： class TreeNode<K,V> { TreeNode<K,V> parent; // 父节点 TreeNode<K,V> left; // 左孩子 TreeNode<K,V> right; // 右孩子 TreeNode<K,V> prev; // 前驱 TreeNode<K,V> next; // 后继 boolean red; // 颜色 } 这种方式需要额外内存来保存前驱和后继指针，那么是不是有一些其它方式来避免这个问题呢？ ...

1. 概述 图1：二叉树遍历 遍历二叉树，即按照某条搜索路径巡访树中的每个结点，使得每个节点均被访问一次，而且仅被访问一次1。 深度优先遍历，常见的有递归方式和用栈实现的迭代方式， Morris 遍历虽然空间复杂度很好，但因需在遍历期间改变树结构而不常用。 广度优先遍历，常见的是用队列实现的迭代方式，但需耗费大量内存，而 IDDFS 算法则更节省内存空间。 本文将主要讲述深度优先遍历的递归和迭代的实现方式，其它见后续文章。 代码仓库：https://github.com/patricklaux/perfect-code 2. 递归 先序遍历、中序遍历和后序遍历的过程完全相同，都是从根到左子树再到右子树，差别仅在于何时访问值。 看后面的代码实现，会发现三段递归程序几乎完全相同，仅仅是调整了访问值的次序。 2.1. 先序遍历 先序遍历 (pre-order traversal)：根，左，右 图2：先序遍历 代码实现 private void preorderTraversalR(List<Tuple2<K, V>> kvs, Node<K, V> p) { // visit，添加到结果集 kvs.add(Tuples.of(p.key, p.val)); if (p.left != null) { preorderTraversalR(kvs, p.left); } if (p.right != null) { preorderTraversalR(kvs, p.right); } } 2.2. 中序遍历 中序遍历(in-order traversal)：左，根，右 中序遍历正好是按键的大小排序。 图3：中序遍历 ...