C++如何手写二叉搜索树（BST）的插入和删除-C++-PHP中文网

bst插入递归需先处理空根：返回新节点；再按值大小递归挂左/右子树并更新指针；删除需分三类：空子节点返nullptr、单子节点用子替代、双子节点用中序后继值覆盖后递归删后继。

c++如何手写二叉搜索树（bst）的插入和删除

插入操作：递归写法最直观，但要注意空节点的处理

BST 插入的核心是找到叶子位置并挂上去。递归写法逻辑清晰，但新手常忽略 root 为 nullptr 时必须返回新节点，否则上层指针不会更新。

如果 root 为 nullptr，直接返回新建节点（不能只 new TreeNode(val) 后不管）
若 val val，递归处理左子树，并用 root->left = insertIntoBST(root->left, val) 接收返回值
同理处理右子树
最后返回 root

示例关键片段：

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val val)
        root->left = insertIntoBST(root->left, val);
    else
        root->right = insertIntoBST(root->right, val);
    return root;
}

删除操作：三种情况必须分开处理，最易错的是“两子节点”情形

BST 删除难点不在找节点，而在删完如何维持 BST 性质。目标节点 node 的子节点数量决定策略：

无子节点：直接 delete node，返回 nullptr
仅一个子节点：用该子节点替代 node（注意是“替换指针”，不是复制值）
两个子节点：找右子树的最左节点（即中序后继），用它的值覆盖 node->val，再递归删除那个最左节点（它必然至多一个子节点）

常见错误：直接交换指针导致内存泄漏，或误用中序前驱（左子树最右）却没统一逻辑；实际工程中推荐固定用中序后继，避免分支混乱。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

为什么不能只改值不删节点？会影响迭代器和指针稳定性

有些实现会把“两子节点”的删除简化为“拷贝后继值 + 删除后继”，看起来少写逻辑，但隐患明显：

如果 TreeNode 包含非 trivial 成员（如 std::string、资源句柄），单纯赋值可能掩盖深拷贝需求
外部若持有指向原节点的指针（比如用于调试或观察者模式），值被覆盖后语义已变，但地址未变，容易引发误判
迭代器（如自定义 BST 迭代器）依赖节点物理位置，替换值不改变结构，但删除+重建才真正反映树形变化

所以标准做法仍是：值覆盖只是过渡手段，最终仍要执行一次真实删除。

手写时别忘了 nullptr 检查和内存释放顺序

C++ 手写 BST 不像 Python 那样有 GC，稍不注意就悬垂指针或重复释放：

所有指针解引用前检查是否为 nullptr，尤其在查找、最小值/最大值函数里
删除节点时，先保存子指针，再 delete 当前节点，最后置空原指针（如 root = nullptr）
递归删除整棵树务必后序遍历：deleteTree(root->left); deleteTree(root->right); delete root;，否则子节点指针失效后无法访问

这些点不体现在算法主干里，但一出错就是段错误或静默数据损坏。