中序前驱不能只看左子树最大节点，因为当节点无左子树时，前驱必为其祖先中第一个作为右孩子被访问的节点；需沿父指针向上回溯或搜索时记录路径。
中序前驱为什么不能只看左子树最大节点
在 BST 中，节点 x 的中序前驱是中序遍历中紧挨在它前面的节点。直觉上容易认为“只要取 x->left 的最右节点就行”，但这个逻辑只在 x 有左子树时成立；如果 x 没有左子树，前驱一定在祖先路径上——而且是第一个“作为右孩子被访问”的那个祖先。
常见错误现象：findPredecessor(nullptr) 崩溃，或对根节点/左叶子节点返回空指针却未向上回溯。
- 必须从目标节点出发，沿父指针（或模拟栈）向上查找，直到遇到某个祖先
p，满足p->right == current - 若节点带
parent指针，可直接迭代回溯；否则需在查找目标时记录路径（如用std::vector<treenode></treenode>） - 无父指针 + 无路径记录 → 无法在 O(h) 时间内完成前驱/后继查找，只能中序遍历一遍缓存所有节点
中序后继的两种实现路径差异明显
后继查找比前驱更常被误写成“取右子树最小节点”而忽略无右子树的情况。关键区别在于：后继要么在右子树最左节点，要么是第一个“作为左孩子被访问”的祖先。
使用场景：实现 std::map::upper_bound 或迭代器 ++it 时必须稳定支持这两种分支。
- 有右子树 → 向下走：循环
current = current->right直到current->left == nullptr - 无右子树 → 向上走：沿父链回溯，找第一个满足
p->left == current的p - 若节点结构不含
parent，推荐在search过程中同步构建路径，避免重复遍历 - 注意：向上查找时，若到达根且仍不满足条件，说明该节点是整棵树最大值，后继为
nullptr
查找目标节点时如何顺便拿到前驱/后继候选
单独调用 find 再调 findSuccessor 会遍历两次树，实际项目中应合并逻辑。核心是在向下搜索过程中，动态维护“最后向左转的节点”和“最后向右转的节点”。
参数差异：多数教程把 findSuccessor 设计为接收已知节点指针，但生产代码中你往往只有 key 值。
- 搜索 key 过程中，每向左走一步，当前节点可能是后继候选（因目标在它左子树，它比目标大）
- 每向右走一步，当前节点可能是前驱候选（因目标在它右子树，它比目标小）
- 这样一次搜索就能同时得到
target、predecessor、successor三个指针，O(h) 时间搞定 - 示例片段：
TreeNode* successor = nullptr;<br>while (root) {<br> if (key val) {<br> successor = root;<br> root = root->left;<br> } else root = root->right;<br>}
delete 节点时前驱/后继选哪个更稳
删除有两个孩子的节点时，标准做法是用前驱或后继覆盖，再删掉那个叶子或单孩子节点。选哪个不是随意的——后继（右子树最小）通常更安全。
性能影响：前驱可能位于很深的左支，后继在右支，但实际深度差异不大；真正要注意的是平衡性退化风险。
- 若 BST 本身右倾严重，频繁用后继替换会导致左子树长期不参与更新，可能加剧不平衡
- 某些实现（如 Linux kernel 的 rbtree）强制用后继，因其能更好配合旋转逻辑
- 如果你的 BST 后续要扩展为 AVL 或红黑树，统一用后继可减少分支判断
- 别忘了：用前驱覆盖后，要删的是原前驱节点 —— 它一定没有右孩子（否则就不是“最大”），但可能有左孩子
前驱和后继的边界处理比想象中琐碎，尤其是空树、单节点、目标为极值节点这三类 case，很容易漏判 nullptr。带 parent 指针的结构能简化逻辑，但会增加插入/删除的维护成本。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
