Morris 二叉树遍历算法
字数 2851 2025-11-15 21:15:09

Morris 二叉树遍历算法

一、问题描述
Morris遍历算法是一种空间复杂度为O(1)的二叉树遍历算法，由J. H. Morris在1979年提出。它可以在不使用递归或栈的情况下，实现二叉树的中序、前序和后序遍历。其核心思想是利用二叉树中大量空闲的指针（叶子节点的空指针）来临时存储信息，从而避免使用额外的存储空间。

二、算法核心思想

  1. 关键观察：在遍历过程中，当我们访问某个节点时，我们需要一种方式能够"回溯"到它的父节点或祖先节点。递归和栈通过隐式或显式地存储路径来实现这一点。Morris算法的巧妙之处在于，它利用叶子节点的空右指针，指向它的中序后继节点，从而在遍历到叶子节点后，能够通过这个临时建立的指针回到需要的地方。

  2. 线索化（Threading）：算法会在遍历过程中临时修改树的结构，建立一种称为"线索"的临时指针。具体来说，对于当前节点curr：

    • 如果curr有左子树，则在curr的左子树中找到它的中序前驱节点（即左子树中最右边的节点）。
    • 将这个前驱节点的右指针指向curr本身。这个指针就像一个"梯子"，帮助我们之后从叶子节点爬回curr。
    • 遍历完成后，这些临时指针会被清除，树的结构会恢复原状。

三、Morris中序遍历
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

步骤详解：

  1. 初始化当前节点curr为根节点。
  2. 当curr不为空时，循环执行以下步骤：
    a. 如果curr没有左子树（curr.left == null）：
    - 访问curr（输出其值）。
    - 将curr设置为其右子节点（curr = curr.right）。注意：这个右子节点可能是真正的右子树，也可能是我们之前设置的指向后继的线索。
    b. 如果curr有左子树（curr.left != null）：
    - 找到curr在中序遍历下的前驱节点pre。pre是curr的左子树中最右边的节点。
    - 从curr.left开始，一直向右子节点走，直到某个节点的右指针为空（pre.right == null）或者指向curr本身（pre.right == curr）。
    - 检查pre的右指针：
    - 如果pre.right == null（第一次访问curr，尚未建立线索）：
    - 将pre.right指向curr（建立线索）。
    - 将curr移动到其左子节点（curr = curr.left），继续处理左子树。
    - 如果pre.right == curr（意味着左子树已经处理完毕，我们通过线索回来了）：
    - 将pre.right重新置为null（恢复树的结构）。
    - 访问curr（现在左子树已访问完，轮到根节点）。
    - 将curr移动到其右子节点（curr = curr.right），开始处理右子树。

示例（中序遍历）：
考虑二叉树：

      1
    /   \
   2     3
  / \   /
 4   5 6

中序遍历结果应为：4, 2, 5, 1, 6, 3

执行过程：

  1. curr=1，有左子树。找前驱：1的左子树是2，2的最右节点是5。5.right初始为null，将其指向1。curr移动到2。
  2. curr=2，有左子树。找前驱：2的左子树是4，4无右子，故前驱是4。4.right初始为null，将其指向2。curr移动到4。
  3. curr=4，无左子树。访问4。curr移动到4.right（即线索指向的2）。
  4. curr=2，再次进入。此时前驱4的right指向2，说明左子树已处理。恢复4.right=null，访问2，curr移动到2的真正右子节点5。
  5. curr=5，无左子树。访问5。curr移动到5.right（线索指向的1）。
  6. curr=1，再次进入。前驱5的right指向1，说明左子树已处理。恢复5.right=null，访问1，curr移动到1的右子节点3。
  7. curr=3，有左子树。找前驱：3的左子树是6，6无右子，故前驱是6。6.right初始为null，将其指向3。curr移动到6。
  8. curr=6，无左子树。访问6。curr移动到6.right（线索指向的3）。
  9. curr=3，再次进入。前驱6的right指向3，恢复6.right=null，访问3，curr移动到3的右子节点（null）。
  10. curr为null，遍历结束。

四、Morris前序遍历
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。只需对中序遍历的代码稍作修改：在第一次到达一个节点时（即建立线索之前）就访问它，而不是在第二次（通过线索回来时）才访问。

步骤修改：
在步骤2b中：

  • 当pre.right == null（第一次访问curr）时：
    • 在建立线索之前，先访问curr。
    • 然后建立线索，并移动curr到左子节点。
  • 当pre.right == curr时（第二次访问）：
    • 恢复结构，不访问curr（因为第一次已经访问过了），直接移动curr到右子节点。

对于上述同一棵树，前序遍历结果应为：1, 2, 4, 5, 3, 6。

五、Morris后序遍历
后序遍历（左子树 -> 右子树 -> 根节点）较为复杂。一种常见技巧是采用"反转"的思路：

  1. 建立一个临时节点（dummy node），让其左子节点指向根节点。
  2. 以类似前序遍历的方式遍历，但将访问顺序改为"右子树 -> 左子树 -> 根节点"（这实际上是原树后序遍历的逆序）。
  3. 在遍历过程中，每当我们"访问"一个节点时，不直接输出，而是将该节点及其路径上的节点顺序反转并存入一个链表，最后再反转整个链表输出。更实用的实现是，在遍历时，每访问一个节点，就将其值插入到结果列表的头部，这样自然就形成了逆序。

由于实现稍复杂，且需要小心处理指针，实践中Morris后序遍历使用较少。

六、算法分析

  • 时间复杂度：O(n)。虽然有嵌套循环（找前驱节点），但每个节点最多被访问两次（一次向下，一次通过线索回来），每条边也被访问常数次，因此总时间是线性的。
  • 空间复杂度：O(1)。只使用了几个指针变量，没有使用递归栈或显式栈。

七、优缺点

  • 优点：极致节省空间，适用于对空间要求苛刻的环境（如嵌入式系统）或遍历非常深的树。
  • 缺点：
    • 算法逻辑相对复杂，容易出错。
    • 在遍历过程中会临时修改树的结构，这在多线程环境下是不安全的。
    • 后序遍历实现复杂，不常用。

Morris遍历是算法设计中的一个经典范例，展示了如何通过巧妙地利用数据结构本身的特性来优化空间复杂度。

Morris 二叉树遍历算法 一、问题描述 Morris遍历算法是一种空间复杂度为O(1)的二叉树遍历算法，由J. H. Morris在1979年提出。它可以在不使用递归或栈的情况下，实现二叉树的中序、前序和后序遍历。其核心思想是利用二叉树中大量空闲的指针（叶子节点的空指针）来临时存储信息，从而避免使用额外的存储空间。 二、算法核心思想 关键观察 ：在遍历过程中，当我们访问某个节点时，我们需要一种方式能够"回溯"到它的父节点或祖先节点。递归和栈通过隐式或显式地存储路径来实现这一点。Morris算法的巧妙之处在于，它利用叶子节点的空右指针，指向它的中序后继节点，从而在遍历到叶子节点后，能够通过这个临时建立的指针回到需要的地方。 线索化（Threading） ：算法会在遍历过程中临时修改树的结构，建立一种称为"线索"的临时指针。具体来说，对于当前节点 curr ： 如果 curr 有左子树，则在 curr 的左子树中找到它的中序前驱节点（即左子树中最右边的节点）。 将这个前驱节点的右指针指向 curr 本身。这个指针就像一个"梯子"，帮助我们之后从叶子节点爬回 curr 。 遍历完成后，这些临时指针会被清除，树的结构会恢复原状。 三、Morris中序遍历 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。 步骤详解： 初始化当前节点 curr 为根节点。 当 curr 不为空时，循环执行以下步骤： a. 如果 curr 没有左子树（ curr.left == null ）： - 访问 curr （输出其值）。 - 将 curr 设置为其右子节点（ curr = curr.right ）。注意：这个右子节点可能是真正的右子树，也可能是我们之前设置的指向后继的线索。 b. 如果 curr 有左子树（ curr.left != null ）： - 找到 curr 在中序遍历下的前驱节点 pre 。 pre 是 curr 的左子树中最右边的节点。 - 从 curr.left 开始，一直向右子节点走，直到某个节点的右指针为空（ pre.right == null ）或者指向 curr 本身（ pre.right == curr ）。 - 检查 pre 的右指针： - 如果 pre.right == null （第一次访问 curr ，尚未建立线索）： - 将 pre.right 指向 curr （建立线索）。 - 将 curr 移动到其左子节点（ curr = curr.left ），继续处理左子树。 - 如果 pre.right == curr （意味着左子树已经处理完毕，我们通过线索回来了）： - 将 pre.right 重新置为 null （恢复树的结构）。 - 访问 curr （现在左子树已访问完，轮到根节点）。 - 将 curr 移动到其右子节点（ curr = curr.right ），开始处理右子树。 示例（中序遍历）： 考虑二叉树： 中序遍历结果应为：4, 2, 5, 1, 6, 3 执行过程： curr=1 ，有左子树。找前驱： 1 的左子树是 2 ， 2 的最右节点是 5 。 5.right 初始为 null ，将其指向 1 。 curr 移动到 2 。 curr=2 ，有左子树。找前驱： 2 的左子树是 4 ， 4 无右子，故前驱是 4 。 4.right 初始为 null ，将其指向 2 。 curr 移动到 4 。 curr=4 ，无左子树。访问 4 。 curr 移动到 4.right （即线索指向的 2 ）。 curr=2 ，再次进入。此时前驱 4 的 right 指向 2 ，说明左子树已处理。恢复 4.right=null ，访问 2 ， curr 移动到 2 的真正右子节点 5 。 curr=5 ，无左子树。访问 5 。 curr 移动到 5.right （线索指向的 1 ）。 curr=1 ，再次进入。前驱 5 的 right 指向 1 ，说明左子树已处理。恢复 5.right=null ，访问 1 ， curr 移动到 1 的右子节点 3 。 curr=3 ，有左子树。找前驱： 3 的左子树是 6 ， 6 无右子，故前驱是 6 。 6.right 初始为 null ，将其指向 3 。 curr 移动到 6 。 curr=6 ，无左子树。访问 6 。 curr 移动到 6.right （线索指向的 3 ）。 curr=3 ，再次进入。前驱 6 的 right 指向 3 ，恢复 6.right=null ，访问 3 ， curr 移动到 3 的右子节点（ null ）。 curr 为 null ，遍历结束。 四、Morris前序遍历 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。只需对中序遍历的代码稍作修改：在第一次到达一个节点时（即建立线索之前）就访问它，而不是在第二次（通过线索回来时）才访问。 步骤修改： 在步骤2b中： 当 pre.right == null （第一次访问 curr ）时： 在建立线索 之前 ，先访问 curr 。 然后建立线索，并移动 curr 到左子节点。 当 pre.right == curr 时（第二次访问）： 恢复结构，不访问 curr （因为第一次已经访问过了），直接移动 curr 到右子节点。 对于上述同一棵树，前序遍历结果应为：1, 2, 4, 5, 3, 6。 五、Morris后序遍历 后序遍历（左子树 -> 右子树 -> 根节点）较为复杂。一种常见技巧是采用"反转"的思路： 建立一个临时节点（dummy node），让其左子节点指向根节点。 以类似前序遍历的方式遍历，但将访问顺序改为"右子树 -> 左子树 -> 根节点"（这实际上是原树后序遍历的逆序）。 在遍历过程中，每当我们"访问"一个节点时，不直接输出，而是将该节点及其路径上的节点顺序反转并存入一个链表，最后再反转整个链表输出。更实用的实现是，在遍历时，每访问一个节点，就将其值插入到结果列表的头部，这样自然就形成了逆序。 由于实现稍复杂，且需要小心处理指针，实践中Morris后序遍历使用较少。 六、算法分析 时间复杂度 ：O(n)。虽然有嵌套循环（找前驱节点），但每个节点最多被访问两次（一次向下，一次通过线索回来），每条边也被访问常数次，因此总时间是线性的。 空间复杂度 ：O(1)。只使用了几个指针变量，没有使用递归栈或显式栈。 七、优缺点 优点 ：极致节省空间，适用于对空间要求苛刻的环境（如嵌入式系统）或遍历非常深的树。 缺点 ： 算法逻辑相对复杂，容易出错。 在遍历过程中会临时修改树的结构，这在多线程环境下是不安全的。 后序遍历实现复杂，不常用。 Morris遍历是算法设计中的一个经典范例，展示了如何通过巧妙地利用数据结构本身的特性来优化空间复杂度。