二叉搜索树中的中序前驱和后继

二叉搜索树 (BST) 是一种著名的数据结构，它以一种允许快速查找、插入和删除的方式存储数据。在使用 BST 时，一个重要的概念是查找节点的**中序前驱**和**中序后继**。节点的**中序前驱**是在 BST 的中序遍历中紧跟在该节点之前的节点。同样，**中序后继**是在中序遍历中紧随在该节点之后的节点。能够快速找到这些节点对于许多 BST 操作都很有用。在本文中，我们将探讨如何在二叉搜索树中查找中序前驱和后继。

中序遍历回顾

在深入讨论前驱和后继之前，让我们快速回顾一下中序遍历。BST 的中序遍历按升序访问节点。它通过递归地遍历左子树、访问当前节点，然后递归地遍历右子树来实现。例如，以下是中序遍历在以下示例 BST 上的工作方式：

节点将按 2、5、8、15、17、20 和 25 的顺序访问。

因此，当我们谈论一个节点的**中序前驱**或**中序后继**时，我们指的是在中序序列中紧随该节点之前或之后的节点。

查找中序前驱

让我们从查找节点的**中序前驱**开始。中序前驱是在中序遍历过程中紧跟在节点之前的节点。

这里有几个关键情况需要考虑：

节点有左子树

如果节点有一个非空的左子树，那么前驱是该子树中最右边的节点。我们可以通过从节点的左子节点开始，并反复跟随右子节点指针直到无法继续来找到它。

例如，在示例树中，15 的前驱是 8。我们从 15 的左子节点 5 开始，然后向右一次到 8。

节点是父节点的左子节点

如果节点是其父节点的左子节点，那么父节点就是前驱。

因此，对于节点 5，它的前驱将是 2（它的父节点）。

节点是父节点的右子节点

如果节点是其父节点的右子节点，那么我们需要递归地向上遍历树，沿着左子节点指针，直到找到一个节点，该节点是其父节点的左子节点。该父节点就是前驱。

17 的前驱是 15，因为 17 是右子节点。所以我们向上到 20，然后沿着它的左子节点指针到 15。

节点没有左子树且不是左子节点

在这种情况下，我们递归地向上遍历树，沿着父节点指针，直到找到满足前面情况之一的节点。

25 的前驱是 20，因为 25 没有左子树且不是左子节点。我们一直遍历到找到 20，它是其父节点的左子节点。

因此，总结一下，要查找中序前驱：

1. 如果节点有左子树，则返回左子树中最右边的节点。
2. 如果节点是父节点的左子节点，则返回父节点。
3. 否则，继续递归向上遍历，直到找到满足 #1 或 #2 的节点。

查找中序后继

可以使用类似的逻辑来查找中序后继，但要反转左右。

后继是在中序遍历过程中紧跟在节点之后的节点。

关键情况是：

节点有右子树

如果节点有一个非空的右子树，那么后继是该子树中最左边的节点。

对于 8，它的后继将是 15，因为 15 是 8 的右子树中最左边的节点。

节点是父节点的右子节点

如果节点是其父节点的右子节点，那么父节点就是后继。

因此，20 的后继是 25。

节点是父节点的左子节点

如果节点是其父节点的左子节点，那么我们递归地向上遍历，寻找一个节点，该节点是其父节点的右子节点。该父节点就是后继。

17 的后继是 20，因为 17 是左子节点。我们向上到 15，然后沿着它的右子节点指针到 20。

节点没有右子树且不是右子节点

在这种情况下，我们一直遍历，直到找到满足其他情况之一的节点。

5 的后继是 8，因为它没有右子树且不是右子节点。我们向上遍历到 15，然后沿着它的右子节点到 8。

总结一下，要查找中序后继：

1. 如果节点有右子树，则返回右子树中最左边的节点。
2. 如果节点是父节点的右子节点，则返回父节点。
3. 否则，继续递归向上遍历，直到找到满足 #1 或 #2 的节点。

Python 实现

方法 1：递归方法

以下是用于在二叉搜索树中查找顺序前驱和后继的递归方法的介绍。

在二叉搜索树 (BST) 中，节点排列方式使得节点的左子树包含小于该节点的值，而右子树包含大于该节点的值。此属性允许我们高效地进行搜索。

BST 的另一个有用属性是，中序遍历访问节点时，它们会按排序顺序访问。称为给定节点之前的节点是它的中序前驱，而紧随其后的节点是中序后继。

我们可以利用这些属性递归地查找给定键的中序前驱和后继。关键思想是递归地遍历 BST，同时跟踪潜在的前驱和后继节点。

当向左遍历时，一个节点成为潜在的前驱。当向右遍历时，它成为可能的后继。一旦我们到达具有匹配键的节点，我们必须查看其左子树和右子树。左子树中的最大值是前驱，右子树中的最小值是后继。

这种递归方法巧妙地利用了 BST 结构来查找前驱和后继，而无需辅助存储。我们不需要维护已访问集合。递归自然地确保我们不会重复工作。这使得解决方案简单而高效。

递归调用充当隐式堆栈来跟踪潜在的候选者。沿着调用堆栈返回即可获得答案。这展示了递归在树问题中的强大功能。总而言之，递归方法直观且最优，它利用了 BST 的内在结构。

程序

输出

Inorder Predecessor: 20
Inorder Successor: 40

说明

1. 定义了 TreeNode 类来表示二叉树的节点。它具有 val、left 和 right 属性。
2. Solution 类包含 findPredecessorSuccessor 方法，用于查找给定键的前驱和后继。
3. findPredecessorSuccessor 将前驱和后继初始化为 None。
4. 它定义了一个 inorderTraversal 辅助函数来以中序方式遍历树。
5. inorderTraversal 递归地遍历左子树。
6. 当找到具有键的节点时，将设置前驱和后继。
   • 如果存在左子节点，则它是前驱。
   • 如果存在右子节点，则它是后继。
7. 使用临时变量来遍历左子树和右子树，以查找最大和最小值的节点。
8. 设置前驱和后继后，中序遍历继续。
9. findPredecessorSuccessor 调用 root 上的 inorderTraversal 来开始遍历。
10. 主代码创建示例树，并调用 findPredecessorSuccessor 来查找键 30 的前驱和后继。
11. 如果找到前驱和后继，则打印它们，否则打印 None。

方法 2：迭代方法

递归方法是一种优雅的解决方案，它利用二叉搜索树的内在结构来查找给定键的前驱和后继。然而，递归有其缺点——它消耗与树高度成比例的堆栈空间，并且涉及函数调用开销。对于非常倾斜或深的树，我们可能会遇到堆栈溢出错误。

另一种选择是采用迭代方法。这里的关键思想是使用指针而不是递归调用来迭代遍历二叉树。我们完全避免了递归。遍历逻辑封装在一个 while 循环中，该循环系统地遍历树节点。

为了跟踪潜在的前驱和后继，我们维护两个引用变量，当我们在遍历过程中进行左转或右转时，这些变量会得到更新。核心是，指针跟踪我们的当前位置，而引用变量跟踪我们到达当前节点的父节点。

一旦找到具有匹配键的节点，引用变量将分别指向前驱和后继，这取决于遍历过程中进行的相对值比较。我们只需要检查节点的左子树和右子树来确认最终值。

这种迭代式遍历仅消耗 O(1) 的辅助空间，因为没有递归堆栈。它在空间效率上更高，并且可以优雅地处理倾斜的树。与递归相比，迭代逻辑也可能更容易理解。总而言之，它通过提供高效且健壮的解决方案来补充递归方法的优雅性。

算法

• 将前驱和后继变量初始化为 None。这些将存储结果。
• 创建一个指针变量 (curr) 来迭代遍历 BST。将其初始化为 root。
• 使用对 curr 的 while 循环来遍历 BST，直到找到匹配键的节点。
• 在进入循环之前，检查 curr 是否为 None 并适当地处理它。
• 在循环内，将 curr 的值与键进行比较。有 3 种情况：
  1. 如果 curr 的值等于键，我们已经找到了节点。检查其左子树和右子树以分别更新前驱和后继变量。跳出循环。
  2. 如果 curr 的值小于键，则更新前驱为 curr，并将 curr 移动到其右子节点。
  3. 如果 curr 的值大于键，则更新后继为 curr，并将 curr 移动到其左子节点。
• 通过迭代地移动 curr 向左和向右，我们递归地遍历 BST，但避免了函数调用开销。
• 前驱和后继节点基本上跟踪我们为了到达键节点而进行左转或右转的父节点。
• 循环结束后，返回前驱和后继变量，它们现在包含结果节点。

优点

• 避免了函数调用和堆栈的递归开销。效率更高。
• 迭代代码通常更易于理解。
• 它可以处理非常深和倾斜的树，而不会导致堆栈溢出。

输出

Inorder Predecessor: 30
Inorder Successor: 40

以下是关于此迭代方法的一些要点：

• 我们初始化 pred 和 succ 为 None 来存储结果。
• 使用 curr 指针来迭代遍历 BST。
• 主 while 循环运行直到我们找到具有匹配键的节点。
• 如果 curr.val == key，我们找到了节点。我们检查其左子树和右子树，分别使用 find_max 和 find_min 辅助函数来填充 pred 和 succ。
• 如果 curr.val < key，curr 成为潜在的前驱，所以我们更新 pred 并将 curr 向右移动。
• 否则 curr.val > key，所以 curr 是潜在的后继。我们更新 succ 并将其移动到 curr 的左侧。
• 一旦找到键并设置了 pred、succ，我们就跳出循环并返回。
• 通过使用 curr 指针进行遍历，我们避免了递归。while 循环迭代遍历 BST。
• pred 和 succ 节点跟踪我们进行左转或右转的祖先节点。
• 当找到键时，pred 和 succ 包含我们最后到达键的节点。
• 检查键的左子树和右子树完成了整个过程。