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

二叉搜索树中节点的前驱是中序遍历中排在其前面的最后一个节点：若有左子树，则为其左子树最右节点；否则为第一个满足该节点位于其右子树的祖先节点。

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

什么是二叉搜索树中的前驱节点

前驱节点指在中序遍历序列中，排在目标节点 node 前面的**最后一个节点**。它不一定是父节点或左子节点——比如当 node 有左子树时，前驱是左子树的最右节点；若没有左子树，则要沿祖先向上找第一个“右拐”来的祖先（即该祖先的右子路径经过了 node）。

如何用迭代方式安全查找前驱（避免递归栈溢出）

递归写法容易在退化成链表的树上爆栈，实际工程中更倾向迭代。核心逻辑分两步：先尝试在左子树里找最右节点；失败则回溯父路径。

从 node->left 出发，持续向 right 走到底，最后非空节点即为前驱
若 node->left 为空，需向上找：设 cur = node，parent 初始为空；循环中若 cur 是 parent->right，则 parent 就是前驱；否则更新 cur = parent，继续上跳
注意：必须提前保存每个节点的父指针，或在查找过程中动态维护（如用栈记录路径），否则无法回溯

为什么不能只靠 parent 指针就直接判断

有 parent 指针也不代表能跳一步得到答案。常见误判是“如果当前节点是右孩子，父节点就是前驱”——这仅在该父节点**没有左子树**时才成立。若父节点有左子树，且该左子树包含比 node 小但比父节点大的值，那前驱其实落在父节点左子树的最右处。

C++ Code Review Master

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

下载

错误写法：if (node == node->parent->right) return node->parent;
正确做法：即使有 parent，仍需检查 node->parent->left 是否存在，若存在，前驱必在其最右节点
所以真正可靠的路径是：先查左子树最右 → 再查祖先中第一个满足“当前节点属于其右子树”的那个祖先

带 parent 指针的 BST 节点定义与前驱实现示例

前提是节点结构含 parent，否则必须改用栈模拟路径。下面是最简可行实现：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *parent;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
};
<p>TreeNode<em> inorderPredecessor(TreeNode</em> node) {
if (!node) return nullptr;
// Case 1: left subtree exists → max in left subtree
if (node->left) {
TreeNode<em> pred = node->left;
while (pred->right) pred = pred->right;
return pred;
}
// Case 2: no left subtree → find first ancestor where node is in right subtree
TreeNode</em> curr = node;
while (curr->parent && curr == curr->parent->left) {
curr = curr->parent;
}
return curr->parent; // if curr is right child, curr->parent is predecessor
}</p>

最后一行的 curr->parent 容易被忽略空指针：若 node 是整棵树最小值（即中序第一个），curr 会一路跳到根，且根无 parent，此时返回 nullptr 才正确。