不使用递归和栈进行中序遍历！

2025年3月17日 | 阅读 7 分钟

通过二叉树的中序遍历，节点的访问顺序是：左子节点，当前节点，然后是右子节点。通常，这个序列被称为“LNR”。

中序二叉树遍历提供了一种系统性的方法来遍历和处理二叉树中的每个节点，从而可以进行打印、搜索或按特定顺序（左、根、右）处理节点等操作。

下面将详细介绍递归中序二叉树遍历。

i) 基本情况：如果当前节点为空，则返回。递归以此作为基本情况。

ii) 访问左子节点：通过左子节点遍历，重复对左子树执行此过程。

iii) 访问当前节点：访问或对当前节点执行操作。在进行中序遍历时，这包括对当前节点执行某些操作，例如打印其值。

iv) 访问右子节点：继续导航到子树的右子节点。

为了在不使用递归或栈的情况下获得所需的中序遍历顺序，通常会临时修改树的结构。使用线索二叉树是一种常见的策略，其中某些节点具有“线索”（指针），可以按正确的遍历顺序将节点“串联”起来。

中序遍历具有多种优势。

有序反向：对于二叉搜索树，中序遍历会按升序遍历节点，这对于查找二叉搜索树中特定节点等活动非常方便。
在许多情况下，中序遍历提供了平衡的树遍历，这对于各种应用程序都很有用。
内存效率高：中序遍历，特别是莫里斯遍历，可以在不使用额外内存结构（如栈）的情况下实现。
非递归方法：中序遍历可以在不使用递归的情况下实现，这在递归可能受限或效率不高的语言或系统中至关重要。

中序二叉树遍历的负面影响

时间复杂度：中序遍历的时间复杂度为 O(n)，其中 n 是树中的节点数。这是因为遍历需要访问每个节点一次。
空间复杂度（使用栈）：在使用栈进行递归或迭代的情况下，空间复杂度可能从 O(h)（其中 h 是树的高度）到 O(n)（最坏情况下，对于斜树）。
修改树结构（莫里斯遍历）：莫里斯遍历方法会暂时修改树的结构，这在不允许此类修改的情况下可能不合适。
中序遍历非常适合按排序顺序查找节点，但对于其他操作（如树重建或某些搜索）可能不是最有效的方法。

递归

递归是一种函数调用自身的编程方法，用于解决问题。递归函数将一个较大的问题分解成更小、相关的子问题，并通过调用自身来解决这些子问题。当达到基本情况时，递归停止，并将答案合并以解决原始问题。递归调用的每一次迭代都会将原始问题分解成更简单的例子。

通常，递归函数包含两个基本部分：

基本情况：规定递归应在何时结束的情况。它是问题最简单的版本，无需进一步递归即可解决。

递归情况：一组规则，规定如何将问题分解成更小的问题并进行

可以分解为相似子问题并经常通过递归解决的问题包括树遍历、阶乘计算以及数学序列的生成。

Stack

栈使用后进先出（LIFO）原则来组织数据，该原则规定最后插入的项是第一个被取出的项。它执行以下两个功能：

Push（入栈）：在栈顶添加一个元素。

Pop（出栈）：移除栈顶元素并替换。

在现实世界中，栈的结构类似于一叠盘子，只能接触到最上面的盘子。在编程中，栈通常用于管理控制流、局部变量和函数调用。

在递归环境中，函数调用栈用于记录函数调用。每当调用一个方法时，都会将具有局部变量和返回值的地址或函数执行所在程序位置的栈推入。当函数完成时，通过弹出其局部变量并返回栈的地址，程序可以继续执行。

总之，递归是一种编程技术，涉及将问题分解为更小、相关的子问题，并递归地解决每个子问题。栈是一种遵循 LIFO 原则的数据结构，通常用于控制函数调用及其上下文。同时，在程序执行期间，尤其是在递归算法中。

树遍历的类型

LNR（左、节点、右）中序遍历

中序遍历包括访问节点的左子树、节点本身，然后是右子树。

- 它对于查找、打印或按排序顺序处理节点等操作很有用，因为在二叉搜索树（BST）中，这种遍历顺序通常用于按升序访问节点。

- 前序遍历（NLR - 节点、左、右）

前序遍历包括按顺序访问节点、左子树，然后是右子树。

- 前序遍历非常适合需要树的自上而下视图的操作，因为它可用于复制树或表示树结构。

LRN（左、右、节点）后序遍历

- 后序遍历包括按顺序访问左子树、右子树，然后是节点本身。

- 在执行需要树的自下而上视图的操作（包括删除树中的所有节点或分析树表示的表达式）时，后序遍历经常被使用。

以下是执行不带递归或栈的中序遍历的一般方法：

修改树以线索化节点：您可以通过修改树结构以包含指向每个节点的线索（指针）来遍历树，而无需使用栈或递归。一个人应该遵循正确的线索指向下一个要访问的节点，以实现正确的遍历顺序。

执行中序遍历：通过在更新后的树中沿着线索移动，按中序遍历顺序进行。

代码

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None
        self.is_threaded = False
        self.thread = None  # Pointer to the next node in order traversal

def create_threads(root, predecessor):
    if the root is None:
        return

    create_threads(root.left, predecessor)

    if predecessor[0] is not None and predecessor[0].right is None:
        # Thread the current node to its in-order successor
        predecessor[0].right = root
        predecessor[0].is_threaded = True
        predecessor[0].thread = "inorder_successor"

    predecessor[0] = root

    create_threads(root.right, predecessor)

def inorder_traversal_without_recursion_and_stack(root):
    current = root
    While current is not None:
        If current. left is None:
            print(current.val)  # Visit the current node
            current = current.right if current.is_threaded else None
        Else:
            # Find the inorder predecessor
            predecessor = current.left
            While predecessor. right is not None and predecessor.right != current:
                predecessor = predecessor.right

            If predecessor.right is None:
                predecessor.right = current  # Thread to inorder successor
                current = current.left
            else:
                predecessor.right = None  # Revert the thread change
                print(current.val)  # Visit the current node
                current = current.right if current.is_threaded else None

# Example usage
# Modify the tree to thread nodes
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
predecessor = [None]  # Pass by reference to track predecessor
create_threads(root, predecessor)

print("Inorder traversal without recursion and stack:")
inorder_traversal_without_recursion_and_stack(root)

输出

Inorder Tree Traversal without recursion and stack!

无需递归和栈的中序二叉树遍历的关键点

莫里斯遍历的效率：它消除了对递归或栈等额外数据结构的需求，并实现了高效的中序二叉树遍历。它具有 O(n) 的时间复杂度和 O(1) 的空间复杂度，内存效率高，适用于具有大量节点的树。
莫里斯遍历不需要额外的数据结构，与传统的递归或基于栈的方法不同，这使得它在内存利用率是一个问题或递归深度可能受限的情况下很有用。
临时修改树结构：该技术使用指针（线索）在节点之间移动，暂时修改树结构。尽管这种修改只是暂时的，并且不会永久改变树，但在使用它时仍需谨慎。
应用：在二叉搜索树中按排序顺序查找节点是中序二叉树遍历的基本操作之一。莫里斯遍历是一种有效的非递归方法来实现这种遍历。
复杂度：尽管莫里斯遍历算法最初看起来很复杂，但它是一种经过验证的经过测试的方法，可以简化中序遍历过程。

结论

总而言之，可以使用莫里斯遍历方法在不使用递归和栈的情况下构建中序二叉树遍历。莫里斯遍历会暂时线索化二叉树，以便高效地按中序序列（左子节点、当前节点、右子节点）遍历节点。

总的来说，莫里斯遍历是一种强大而有效的方法，它在内存使用和遍历效率之间取得了平衡，使其成为计算机编程中树遍历操作的重要工具。莫里斯遍历支持无需递归和栈的中序二叉树遍历。

下一主题左右两侧下一个更大元素的索引的最大乘积