C++如何实现二叉搜索树中指定节点的前驱节点查找-C++-PHP中文网

前驱节点是bst中序遍历中目标节点的前一个节点，即比其值小的最大节点；有左子树时为其左子树最右节点，无左子树时为向上回溯中首个作为右孩子的祖先节点。

c++如何实现二叉搜索树中指定节点的前驱节点查找

什么是前驱节点，它在BST里长什么样

前驱节点指中序遍历中位于目标节点 node 前面的那个节点。对 BST 来说，它的本质是：比 node->val 小的所有值里的最大者。

所以分两种情况：

如果 node 有左子树，前驱就是左子树的「最右节点」（即左子树中序遍历的最后一个）
如果 node 没有左子树，就得往上找——从父节点开始回溯，直到第一次「从右孩子返回父节点」的位置，那个父节点就是前驱

不带 parent 指针时怎么安全地向上回溯

多数实现中 TreeNode 不含 parent 字段，没法直接跳父节点。这时候必须边查找目标节点边记录路径，或者用递归隐式栈保存祖先信息。

推荐用递归方式，在查找过程中维护一个「可能的前驱候选」：

初始候选为 nullptr
每次向右走（说明当前节点值小于目标，可能是前驱）时更新候选为当前节点
每次向左走时候选不变
找到目标后，候选就是前驱；没找到则返回 nullptr

示例逻辑片段：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

TreeNode* findPredecessor(TreeNode* root, int target) {
    TreeNode* pred = nullptr;
    while (root) {
        if (root->val >= target) {
            root = root->left;
        } else {
            pred = root;
            root = root->right;
        }
    }
    return pred;
}

带 parent 指针时的简洁解法

如果有 parent 字段，逻辑更直观，但要注意两个分支的边界处理：

左子树存在 → 走到左子树的最右节点（循环 while (node->left) 然后 while (node->right)）
左子树不存在 → 向上找第一个「是其父节点右孩子的祖先」，即 node == node->parent->right 成立时，node->parent 就是前驱
如果一路回溯到根都没满足条件，说明目标是整棵树最小值，无前驱 → 返回 nullptr

注意：判断 node->parent 是否为空必须放在每次访问前，否则会访问空指针。