C++实现二叉搜索树BST _ 插入删除与查找操作【源码】

关于BST操作，这里有几个核心判断：插入操作需要递归返回新子树根，注意空指针；查找推荐用迭代，避免栈溢出；删除要分三种情况处理，双子节点要用中序后继并更新父指针；析构必须后序遍历，new/delete要配对。

插入操作：递归实现比迭代更直观，但要注意空指针解引用

插入操作说白了，就是找到那个值该待的叶子位置，然后把它挂上去。递归写法跟BST的树形结构天然契合，逻辑上很清晰。不过，新手容易犯的一个错误是，在判断 `root == nullptr` 之前就去访问 `root->val`，这直接导致段错误。 关键点有这么几个： * 递归函数必须返回 `TreeNode*`，这样才能向上回传新的子树根——特别是在插入到空位置时，需要 `new` 一个节点。 * 比较之后只走一个分支：`val < root->val` 走左子树，否则走右子树。相等的情况一般不插入，因为BST通常不存储重复值。 * 别忘了给子节点赋值：`root->left = insertIntoBST(root->left, val);` 这句漏掉的话，相当于白递归了一遍。 示例代码：

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

查找操作：迭代写法更省内存，且天然避免栈溢出风险

查找操作不涉及修改树结构，纯遍历，用迭代写法既简洁又安全。递归虽然代码短，但在极端情况下（比如左斜或右斜树，退化成链表）很容易导致栈溢出，生产环境里优先考虑迭代。 需要警惕的细节： * 循环条件写成 `root != nullptr` 没问题，但内部如果忘了更新 `root`，就会陷入死循环。 * 查不到时返回 `nullptr` 是惯例，不过调用方如果直接解引用而不判空，照样会崩溃。 * 不要在循环里 `new` 或 `delete`——查找操作不该有副作用。 代码示例：

TreeNode* searchBST(TreeNode* root, int val) {
    while (root && root->val != val) {
        root = (val < root->val) ? root->left : root->right;
    }
    return root;
}

删除操作：三种情况必须分清，后继替换时要小心指针“悬空”

删除操作是BST里最容易出错的地方。节点无子、单子、双子，处理方式完全不同。最麻烦的是双子节点：必须用中序后继（也就是右子树最左节点）来替换，替换之后还得把后继节点从原位置摘掉——这一步很容易漏掉对后继父节点的更新。 实操要点： * 无子节点：直接 `delete root; return nullptr;` * 单子节点：让子节点顶上来，`return root->left ?: root->right;` * 双子节点：找后继（不是后继的值，是后继节点本身），用它的值覆盖当前节点，再递归删除后继。注意，此时递归调用的是 `deleteNode(root->right, successor->val)`，而不是传 `successor` 地址。 * 所有 `delete` 之后，建议把对应指针置为 `nullptr`（调试阶段尤其有用），避免野指针误用。

内存管理：析构函数必须后序遍历，new 和 delete 要严格配对

很多教程只讲核心操作，却忽略了资源清理。如果BST长期运行或者频繁构造、销毁，不写析构函数就会导致内存泄漏。更糟糕的是，如果用前序或中序顺序释放，会提前删掉子树根，导致子节点丢失，无法访问。 正确做法： * 析构函数内先递归删左、再删右、最后 `delete this`。 * 如果类封装了 `root` 成员，确保构造函数初始化为 `nullptr`，拷贝/移动语义按需实现（否则浅拷贝会引发 double free）。 * 使用智能指针（比如 `std::unique_ptr`）可以省去手动 `delete`，但需要重写所有操作接口以适配指针解引用（例如 `root->left.get()`）。 裸指针版的析构示意：

void destroy(TreeNode* node) {
    if (!node) return;
    destroy(node->left);
    destroy(node->right);
    delete node;
}

真正难的不是单独写对某个操作，而是所有操作在边界条件下（空树、单节点、重复值、大规模数据）仍然能保持结构不变性和内存安全——这些地方一漏，调试成本可比实现本身高多了。