有左子树的节点的中序前驱一定是二叉搜索树中的叶节点吗？

Question

在二叉搜索树（BST）中，我试图理解中序前驱的属性，特别是对于具有左子树的节点。

定义：节点的中序前驱是其左子树中的最大节点。

观察：我很好奇当相关节点有左子树时，有序前驱是否始终是叶节点。

考虑以下 BST：

      5
     / \
    3   7
   / \
  2   4

在这棵树中：

节点 3（有左子树）的中序前驱是 2。 节点 2 是叶节点。

问题：

我的理解正确吗？

此规则有任何例外吗？

BST 中有序前驱的一般性质是什么？

谢谢您的帮助！

Answer 1

这并不（总是）正确。

如果节点 𝑢 具有以 𝑣 为根的左子树，则 𝑢 的有序前驱是在以 𝑣 为根的子树中具有最大键的节点 𝑤。 𝑤 是位于从 𝑤 开始的最长向下路径末端的节点，不包括向左的边。因此，𝑤（有序前身）没有右子树。但对其潜在的左子树没有约束。

例如，采用二叉搜索树：

                    ___20___
                   /        \
                __8__        30
               /     \      /
              4      12    23
             / \     /    /  \
            2   6  10    21   27
           /   /  /  \       /
          1   5  9   11     25

4 的前驱是 2，它有一个左孩子 (1)。 8 的前身是 6，它还有一个左孩子 (5)。 20 的前驱是 12，它有一个左子树（根为 10）。 30 的前身是 27，它有一个左孩子 (25)。例子足以说明这些前辈不一定是叶子。

共同的不变量是这些前辈没有右孩子。

BST 中有序前驱的一般性质是什么？

在general中——所以不仅在查看具有左子树的节点时——节点的前任可以是BST中的任何节点，除了具有最大值的节点。显然是这样，因为所有这些节点都有一个后继者，所以它们是后继者的前任。

特别是，当一个节点没有左子树时，那么它的前任（如果有的话）必然是一个有右子树的节点。这是我们对您的情况的“相反”条件，因此根据左子树或右子树的存在，前辈没有识别属性。