bst中序前驱是比当前节点小的最大节点：若有左子树则为其最右节点，否则向上回溯找首个右孩子路径含当前节点的祖先；后继同理对称。需维护parent指针并严格空指针防护。
中序前驱节点：如何在BST中找到比当前节点小的最大节点
BST的中序前驱，就是中序遍历中紧挨在当前节点前面的那个节点。它不依赖全局遍历，而应利用BST左小右大的结构特性直接定位。
关键判断逻辑是：如果当前节点有左子树，前驱一定在其左子树的最右节点（即左子树中最大的节点）；否则，需要向上回溯，找第一个“其右孩子路径包含当前节点”的祖先——也就是沿父指针向上走，直到遇到某个祖先节点 p，满足 p->right == current，那么 p 就是前驱。
实操注意点：
- 必须为节点维护
parent指针，否则无法向上回溯；若无parent，只能中序遍历缓存全部节点再查索引，时间/空间开销大 - 查找最右节点时，循环条件是
node && node->right，不能漏掉node非空判断 - 向上回溯时，要避免无限循环：必须确保只在
current是其父节点右孩子时才继续上跳，否则立刻终止
中序后继节点：如何在BST中找到比当前节点大的最小节点
后继节点正好与前驱对称：若有右子树，则为右子树的最左节点；否则向上找第一个“其左孩子路径包含当前节点”的祖先，即沿 parent 向上，直到 p->left == current 成立，p 即为后继。
常见错误现象：nullptr 解引用——比如未检查 current->right 就直接进入右子树找最左，或在回溯时没判断 current->parent 是否为空就访问 current->parent->left。
实操建议：
- 找最左节点的循环写法统一用
while (node && node->left) node = node->left，兼顾空指针安全 - 回溯循环中，每次更新前先保存当前节点为
child，再令current = current->parent，然后判断current && current->left == child - 若节点无右子树且回溯到根仍不满足
current->left == child，说明该节点是整棵树最大值，无后继，返回nullptr
为什么不能只靠中序遍历数组索引来找前驱/后继
虽然中序遍历能生成有序序列，但每次查询都做一次遍历（O(n)）或预存整个序列（O(n)空间），完全浪费了BST的结构优势。实际应用中，如实现 std::set 的 lower_bound 或迭代器自增/自减，必须支持 O(h) 单次查询（h 为树高）。
性能影响明显：
- 平衡BST下，
findSuccessor是 O(log n)，而中序遍历是 O(n) - 退化成链表时，前者仍是 O(n)，后者也是 O(n)，但常数更大（需建数组、两次遍历）
- 若只查一次还凑合，但连续调用（如遍历所有节点）时，遍历法总代价 O(n²)，而逐个调用后继是 O(n) 总耗时
C++实现中容易被忽略的边界细节
很多开源实现漏掉这些检查，导致运行时崩溃或逻辑错误：
-
parent指针在插入/删除时未正确维护——特别是旋转操作（AVL/RB树）中，parent更新遗漏一处就会让后继查找失效 - 节点值相等时的行为：标准BST不允许重复值，但若业务允许重复且插入到右子树，则前驱可能出现在左子树的最右，也可能出现在父路径上，需明确定义比较逻辑
- 使用
std::unique_ptr管理节点时，parent不能也用unique_ptr（会形成循环引用），必须用裸指针或weak_ptr，否则析构失败 - 查找函数返回类型应为
Node*而非const Node*，否则无法用于后续修改场景（如删除后继再替换）
真正难的不是算法本身，而是把 parent 维护、空指针防御、内存模型这三件事在所有增删改路径里始终如一地贯彻下去。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
