C++实现二叉搜索树BST的节点前驱查找 _ 指针遍历逻辑深度解析【源码】-C++-PHP中文网

前驱节点是BST中比目标节点小的最大节点；有左子树时为其左子树最右节点，无左子树时需向上回溯首个作为右子节点的祖先，无则不存在。

c++实现二叉搜索树bst的节点前驱查找 _ 指针遍历逻辑深度解析【源码】

前驱节点是什么，为什么不能只靠左子树最大值

在 BST 中，某个节点的前驱是比它小的最大节点。很多人第一反应是“往左走到底再往右”，但这是错的——如果目标节点没有左子树，前驱根本不在左子树里，而是在向上回溯路径中某个祖先节点上。比如节点 15 的左子树为空，它的前驱是父节点 10（假设结构为 10→right=15），这时必须沿父指针向上找第一个“被右子树访问过”的祖先。

带 parent 指针的查找逻辑怎么写才不漏情况

有 parent 指针时，分两种主路径：

若节点有左子树：前驱就是左子树中的最右节点（即 left→right→right→… 直到 right == nullptr）
若节点无左子树：从当前节点开始向上遍历 parent，直到遇到第一个满足 node == parent->right 的祖先，该祖先就是前驱；如果一路上都是 node == parent->left，说明当前节点是最小值，无前驱

注意：parent 指针必须在插入/构造时正确维护，否则向上遍历会崩溃或逻辑错乱。

不带 parent 指针时如何用递归模拟回溯路径

没有 parent 就得靠递归隐式栈“记住来路”。核心是传入一个候选前驱变量（如 TreeNode* prev），并在中序遍历过程中更新它：

TreeNode* findPredecessor(TreeNode* root, int target, TreeNode*& prev) {
    if (!root) return nullptr;
    if (root->val == target) return prev; // 找到目标，返回当前记录的前一个
    if (target val) {
        return findPredecessor(root->left, target, prev);
    } else {
        prev = root; // 当前节点比 target 小，可能是候选
        return findPredecessor(root->right, target, prev);
    }
}

这个写法本质是“边搜索边记最后一个小于 target 的节点”，不依赖子树结构，但要求调用前将 prev 初始化为 nullptr。容易漏掉的点是：没处理 target 不在树中的情况，此时返回的 prev 是小于它的最大存在节点（不是错误，但需明确语义）。