c++oding="utf-8" ?>
前驱节点不总在左子树中：若节点有左子树，则前驱为其左子树最右节点；若无左子树，则需向上回溯，找第一个是其父节点右孩子的祖先，该父节点即为前驱。
中序前驱为什么不能只看左子树最大节点
因为前驱是中序遍历中当前节点的上一个节点，它不一定在左子树里——当节点没有左子树时，前驱是某个祖先节点。比如根节点无左子树，它的前驱只能向上找第一个“被右分支访问”的祖先。
实操建议：
- 从目标节点出发向上回溯
parent指针，找第一个满足「该节点是其父节点右孩子」的祖先，那个父节点就是前驱 - 若节点有左子树，则前驱一定是左子树中的最右节点（不断走
right直到空） - 必须保证每个节点存有
parent指针，否则无法高效向上查找；若无parent，只能中序遍历缓存全部节点再查索引，O(n) 时间
中序后继的两种路径怎么选
后继是中序遍历中当前节点的下一个节点，分两种情况处理，逻辑刚好和前驱对称：
- 若节点有右子树：后继 = 右子树中最左节点（循环走
left直到空） - 若节点无右子树：向上找第一个「该节点是其父节点左孩子」的祖先，那个父节点即为后继
- 注意边界：若节点是整棵树最右节点（无右子树且一路都是父节点的右孩子），则后继不存在，返回
nullptr
常见错误现象：Segmentation fault 多因未判空就访问 parent->left 或 parent->right；建议每次使用 parent 前先检查是否为 nullptr。
查找前驱/后继时 parent 指针为空怎么办
很多教材实现的 BST 节点不带 parent，此时无法 O(h) 完成查询，必须降级为模拟中序遍历过程。
实操建议：
- 用栈手动模拟递归：从根开始，沿左链压栈，直到目标节点或更早位置；过程中记录路径，便于定位前一/后一节点
- 或者一次完整中序遍历（
std::vector存节点指针），再用二分或线性扫描找目标索引 —— 空间 O(n)，时间 O(n)，仅适合离线批量查 - 如果高频查前驱/后继，重构节点结构加
parent字段是更实际的选择，比每次遍历划算得多
std::set 迭代器的 next/prev 本质是不是 BST 前驱后继
是，但不是你手写的 BST。libstdc++ 和 libc++ 的 std::set 底层是红黑树，std::next(it) 和 std::prev(it) 就是调用内部等价于前驱/后继的常数均摊操作。
性能与兼容性影响：
- 它们不依赖用户提供的
parent指针，而是通过树结构+颜色位+子节点关系在 O(log n) 内完成，且无额外空间开销 - 但你无法直接复用这套逻辑——标准库不暴露红黑树节点结构，
std::set::iterator是封装过的，不可解引用为原始节点指针 - 想验证行为？可写对比测试：对你手写的 BST 和
std::set同时插入相同序列，用相同 key 查后继，输出地址或值比对
真正容易被忽略的是：手写 BST 中，parent 指针的维护必须贯穿所有修改操作（insert/delete），漏掉一处，前驱/后继就会静默出错。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
