没有左子树且作为其父节点的左子节点的节点的中序前驱节点是否始终是其祖节点？

Question

我正在尝试了解在二叉搜索树（BST）中查找节点的中序前驱的规则。

• 如果节点𝑥有左子树，则中序前驱是 该左子树中的最大值。

• 如果节点𝑥没有左子树， 前身是它的祖先之一。但如果节点 𝑥 是右子节点，那么它的父节点 p 就是它的前驱

这是我的具体问题：

如果节点𝑥没有左子树并且是其父节点的左孩子，则其父节点𝑝不能是前驱节点，因为𝑝大于𝑥。在这种情况下，我们沿着树向上移动以找到小于 𝑥 的祖先，并且该祖先是 𝑥 的前身。

看看这个 BST：

         50
        /  \
      30    70
     /  \
   20   40
       /
      35

• 节点 𝑥 = 35 没有左子树，并且是其父节点的左子树
• 40（父级）不能是中序前驱，因为它更大 超过 35。
• 我们将树向上移动到 40 的父级，即 30。
• 30 比 35 小，所以 30 是 35 的中序前身。

在这种情况下，节点 𝑥 的有序前身是否始终是其祖父母，或者可能是更远的祖先？

Answer 1

它是左边的第一个父级。 你可能不得不上升任意远：

    0
   / \
      4
     / \
    3
   / \
  2
 / \
1