C++ 实现二叉搜索树 BST 的中序前驱与后继查找 _ 节点搜索【源码】

先说一个常见的认知误区：很多人觉得，找中序前驱嘛，直接取左子树最右边的节点就行了。其实这个结论只在节点有左子树时成立——要是没有左子树，前驱就得从祖先路径里找，而且是第一个“作为右孩子被访问”的那个祖先。这一点恰恰是大多数实现容易翻车的地方。

中序前驱为什么不能只看左子树最大节点

在 BST 里，节点 x 的中序前驱，就是中序遍历时紧挨在它前面的那个节点。直觉上，很多人会想：这不简单吗，取 x->left 的最右节点就行。但注意，这个逻辑只在 x 有左子树时成立。如果 x 没有左子树，前驱一定在祖先路径上——而且是第一个“作为右孩子被访问”的那个祖先。

常见的问题场景包括：findPredecessor(nullptr) 直接崩溃，或者对根节点或左叶子节点返回空指针，但压根没考虑向上回溯。

• 必须从目标节点出发，沿着父指针（或模拟栈）向上走，直到遇到某个祖先 p，满足 p->right == current。
• 如果节点带 parent 指针，直接迭代回溯就行；否则，需要在查找目标时记录路径（比如用 std::vector 存下来）。
• 没有父指针，又不记录路径？那对不起，只能中序遍历一遍，把所有节点缓存起来，再找前驱后继——时间复杂度直接变成 O(n)。

中序后继的两种实现路径差异明显

后继查找比前驱更容易被误写。很多人一拍脑袋：“取右子树最小节点嘛”，然后就把无右子树的情况忘得一干二净。关键区别在于：后继要么在右子树最左节点，要么是第一个“作为左孩子被访问”的祖先。

这个逻辑在实现 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;
  while (root) {
    if (key < root->val) {
      successor = root;
      root = root->left;
    } else root = root->right;
  }

delete 节点时前驱/后继选哪个更稳

删除有两个孩子的节点时，标准做法是用前驱或后继的值覆盖，然后再删掉那个叶子或单孩子节点。选哪个不是随意的——从稳定性来看，后继（右子树最小）通常更安全。

性能方面，前驱可能位于很深的左支，后继在右支，但实际深度差异不大。真正需要注意的，是平衡性退化风险。

• 如果 BST 本身右倾严重，频繁用后继替换会导致左子树长期不参与更新，可能加剧不平衡。
• 某些实现（比如 Linux kernel 的 rbtree）强制用后继，因为它能更好地配合旋转逻辑。
• 如果你的 BST 后续要扩展为 A VL 或红黑树，统一用后继可以减少分支判断。
• 别忘了：用前驱覆盖后，要删除的是原前驱节点——它一定没有右孩子（否则就不是“最大”），但可能有左孩子。

前驱和后继的边界处理，比想象中要琐碎得多。空树、单节点、目标为极值节点，这三类 case 很容易漏判 nullptr。带 parent 指针的结构能简化逻辑，但会增加插入/删除的维护成本——这本身就是个权衡。