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

前驱节点是二叉搜索树中比某节点小的最大节点，有左子树时为其左子树最右节点，无左子树时需向上回溯找首个作为右孩子的祖先；依赖parent指针实现o(h)查询，否则退化为o(n)。

c++如何实现二叉搜索树的前驱节点查询逻辑

前驱节点是什么，什么时候需要它

二叉搜索树（BST）中，某个节点的前驱节点是指比它小的最大节点。这在实现 std::set 或 std::map 的迭代器自减（--it）、有序遍历中找“上一个”元素、或者实现有序集合的区间查询时很关键。

它不是简单地往左走到底——只有当目标节点有左子树时，前驱才是左子树的最右节点；否则得向上回溯，找第一个“作为右孩子被访问”的祖先。

有左子树时：直接找左子树最右节点

这是最常见也最简单的路径。只要 node->left 非空，前驱一定在左子树里，且是其中值最大的节点，也就是一直往右走到叶子。

Node* predecessor(Node* node) {
    if (!node) return nullptr;
    if (node->left) {
        Node* p = node->left;
        while (p->right) p = p->right;
        return p;
    }
    // 否则需向上查找
}

注意：这里不检查 p 是否为空，因为已确认 node->left 存在，所以 p 至少是那个左孩子。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

无左子树时：向上回溯找“第一个右分支祖先”

此时前驱不在左子树，必须沿父指针往上找。目标是找到最近的一个祖先，使得当前节点位于它的右子树中——因为只有这种情况下，该祖先才比当前节点小，且是满足条件的最大者。

需要节点结构里有 parent 指针（STL 容器内部节点通常都有）
从当前节点开始，不断往上走，直到出现 cur == cur->parent->right
一旦满足，cur->parent 就是前驱；如果一路走到根都没满足，说明当前节点是整棵树最小值，无前驱

Node* predecessor(Node* node) {
    if (!node) return nullptr;
    if (node->left) {
        Node* p = node->left;
        while (p->right) p = p->right;
        return p;
    }
    // 向上找第一个“我是它右孩子”的祖先
    while (node->parent && node == node->parent->left) {
        node = node->parent;
    }
    return node->parent; // 可能为 nullptr（无前驱）
}