二叉搜索树中带左子树节点的中序前驱是否必为叶子节点？

你的理解是否正确？有没有例外？ #

你的理解不正确，带左子树的节点的中序前驱不一定是叶子节点。

举个反例：

10
     /
    7
   / \
  5   9
     /
    8

在这个BST中，节点10存在左子树（以7为根），它的中序前驱是左子树中的最大节点——9。但9并非叶子节点，它有左子节点8。这就打破了“前驱一定是叶子节点”的假设。

再看节点7的中序前驱是左子树最大节点5（叶子节点），节点9的中序前驱是8（叶子节点）。可见，前驱是否为叶子节点完全取决于左子树的结构，没有必然规律。

BST中序前驱的通用特性 #

• 对于存在左子树的节点，其中序前驱是其左子树中的最大节点：即从左子节点出发，一直沿着右指针走到尽头的节点。这个节点可能是叶子节点，也可能是带有左子节点的非叶子节点（如上面例子中的9）。
• 对于没有左子树的节点，其中序前驱是最近的祖先节点：需要沿着父节点向上遍历，直到找到一个节点是其父节点的右孩子——这个父节点就是目标节点的中序前驱。如果目标节点是整棵树的最左节点（最小元素），则不存在中序前驱。
• 中序前驱的键值一定小于目标节点的键值（符合BST的性质），且是所有小于目标节点的键值中最大的那个。

内容的提问来源于stack exchange，提问作者Aslam Sha