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

前驱节点是BST中序遍历中位于目标节点前的节点，即比其值小的最大节点；有左子树时为其左子树最右节点，否则为查找路径上最后一个右拐的祖先。

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

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

前驱节点是指中序遍历中位于目标节点 node 之前的那个节点。对 BST 来说，它要么是 node 左子树的最右节点（左子树存在时），要么是向上回溯过程中第一个“右拐”来的祖先（左子树为空时）。

注意：前驱节点一定比 node->val 小，且是所有比它小的值中最大的那个——这正是 BST 的结构性质决定的，不是靠遍历全树找出来的。

有左子树时怎么快速拿到前驱

如果 node->left 非空，前驱就在左子树里，而且一定是左子树的“最右叶子或非叶子节点”。不需要递归整棵树，只需一路向右：

TreeNode* predecessor = node->left;
while (predecessor->right) {
    predecessor = predecessor->right;
}
// 此时 predecessor 就是前驱

这个过程时间复杂度是 O(h)，h 是左子树高度，远优于中序遍历再查索引
别漏判 predecessor->right == nullptr 的退出条件，否则空指针解引用
即使 node->left 是个单链（只有 left 没 right），循环一次都不进，predecessor 就是它自己——这也符合定义

左子树为空时怎么向上找“第一个右拐祖先”

这时得从根开始向下查找 node，同时记录可能的前驱候选。更实用的做法是：沿查找路径维护一个变量，每次往右走时更新它（因为往右意味着当前节点值比目标小，可能是前驱）：

C++14

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

下载

TreeNode* findPredecessor(TreeNode* root, TreeNode* node) {
    TreeNode* pred = nullptr;
    TreeNode* cur = root;
    while (cur != node) {
        if (cur->val val) {
            pred = cur;      // 往右走，当前节点可能是前驱
            cur = cur->right;
        } else {
            cur = cur->left;
        }
    }
    // 找到 node 后，如果它有左子树，上面逻辑不适用，要另走左子树最右
    if (node->left) {
        cur = node->left;
        while (cur->right) cur = cur->right;
        return cur;
    }
    return pred;
}