C++如何实现二叉搜索树的后继节点查询-C++-PHP中文网

后继节点是bst中比当前节点值大的最小节点；有右子树时为其右子树最左节点，无右子树时为第一个作为左孩子的祖先，不带parent指针时可从根预存候选者实现o(h)时间复杂度。

c++如何实现二叉搜索树的后继节点查询

后继节点是什么，为什么不能只靠中序遍历找

后继节点指在二叉搜索树（BST）中，比当前节点值大的最小节点。很多人第一反应是“跑一遍中序遍历，记录所有节点，再查下一个”——这在静态树里可行，但实际场景（比如在线查询、频繁插入删除）下，时间复杂度 O(n) 太重，且无法利用 BST 的结构优势。

真正高效的做法必须基于树结构本身，分两种情况处理：
- 如果节点有右子树，后继一定是右子树的最左节点；
- 如果没有右子树，则要向上回溯，找第一个“作为左孩子被访问”的祖先。

有右子树时怎么找最左节点

这是最简单也最常被写错的地方：不是直接返回 right，而是不断往左走到尽头。

从 node->right 开始，循环判断是否非空，每次走 current = current->left
终止条件是 current->left == nullptr，此时 current 就是后继
注意边界：如果 node->right 为空，这个分支根本不该进入

TreeNode* successor = node->right;
while (successor->left != nullptr) {
    successor = successor->left;
}

无右子树时如何向上找“第一个左孩子祖先”

这个逻辑容易绕晕。核心是：从当前节点出发，沿着父指针往上走，直到某次是从左子树上来的（即当前节点是其父节点的左孩子），那个父节点就是后继。

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

需要节点结构包含 parent 指针（否则无法实现 O(h) 时间）
用循环判断 node == node->parent->right：如果是，说明当前节点是右孩子，继续向上；如果不是（即 node == node->parent->left），就找到了
如果一路走到根都没找到，说明当前节点是整棵树最大值，无后继，返回 nullptr

TreeNode* parent = node->parent;
while (parent != nullptr && node == parent->right) {
    node = parent;
    parent = parent->parent;
}
return parent;