前驱节点是值严格小于x->val的最大节点，要么为x左子树最右节点，要么为向上路径中首个使x位于其右子树的祖先；后继则对称，为右子树最左节点或首个使x在其左子树的祖先。
前驱节点怎么找：核心是“左子树最右”或“向上找第一个右拐”
BST 中某节点 x 的前驱，是指值严格小于 x->val 的最大节点。它要么在 x 的左子树里（此时一定是左子树的最右节点），要么在向上回溯路径上（当 x 是其父节点的左孩子时，前驱就是第一个让 x 处于其右子树的祖先）。
实操建议：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 先检查
x->left是否非空：若存在，一路right到底，最后那个非空节点就是前驱 - 否则从根开始向下查找：维护一个
predecessor变量，每次走root->val val时更新它，然后向右；否则向左 - 注意：不能直接用 parent 指针暴力回溯——很多实现没存 parent，且即使有，也要避免重复访问或空指针解引用
- 常见错误是把“等于”当作可接受条件，但前驱定义要求严格小于，
val == x->val的节点不算
后继节点怎么找：对称逻辑，“右子树最左”或“向上找第一个左拐”
后继是值严格大于 x->val 的最小节点。和前驱完全对称：要么是 x->right 的最左节点，要么是向上路径中第一个让 x 落在其左子树的祖先。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 若
x->right存在，就一直往left走，直到left == nullptr，上一个非空节点即后继 - 否则从根出发搜索：维护
successor，每次root->val > x->val时更新它，然后向左；否则向右 - 和前驱一样，别混淆“大于等于”——
val == x->val的节点不满足后继定义 - 性能上，两种查找都是 O(h)，h 是树高；退化成链表时会到 O(n)，无法靠查找本身优化，得靠平衡树结构（如 AVL 或红黑树）保障
为什么不能只靠 parent 指针做前驱/后继？
很多人一想到“向上找”，就默认加 parent 成员，但这会引入三类实际问题：
- 插入/删除逻辑变复杂：每次调整树结构都得同步更新
parent，漏掉一处就会导致指针野指针或循环引用 - 内存开销增加：每个节点多 8 字节（64 位系统），对海量节点场景影响明显
- 并非所有 BST 实现都带
parent—— STL 的std::set和std::map内部节点就不暴露 parent，你没法依赖它 - 真正稳定的写法是“无 parent 依赖”的搜索逻辑，和
find类似，只是多记一个候选节点
手写 BST 时如何验证前驱/后继是否正确？
最容易忽略的是边界情况，比如叶子节点、只有单边子树的节点、根节点本身，以及空树或单节点树。
建议这样验证：
- 对任意节点
x，调用predecessor(x)后，检查返回指针是否非空，且pred->val val；再手动确认没有其他节点值落在(pred->val, x->val)区间内 - 类似地，对
successor(x)，确保succ->val > x->val，且区间(x->val, succ->val)为空 - 特别测试
x是最小值（无前驱）或最大值（无后继）的情况：函数应返回nullptr，而不是崩溃或返回错误节点 - 别忘了空树输入：传入
nullptr给predecessor或successor，必须安全返回nullptr
这些边界点一旦漏掉一个，上线后可能只在特定数据分布下才暴露，调试成本远高于写的时候多加两行判断。
