C++如何实现二叉搜索树的插入-C++-PHP中文网

bst插入的核心逻辑是找到满足left

c++如何实现二叉搜索树的插入

插入操作的核心逻辑是什么

二叉搜索树（BST）插入的本质是：找到值该落脚的空位置，然后挂上去。不是递归或迭代本身重要，而是必须严格满足 left 的结构约束。一旦插错位置，整棵树就不再是 BST，后续查找、删除都会出错。

插入前必须从根开始比较，一路向下找“应该放哪”
遇到空指针（nullptr）时才真正插入新节点，不能提前新建再比较
每次比较只决定往左还是往右，不修改当前节点内容

递归实现怎么写才不会漏掉返回值

C++ 里用递归插入，最常踩的坑是：忘了把子树的新根返回给父节点更新指针。因为 C++ 默认传值，root->left = insert(root->left, val) 这一步不可省——哪怕 root->left 原来是 nullptr，也得靠赋值把新节点链上去。

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

函数必须返回 TreeNode*，调用方要用它更新左右指针
不要写成 void insert(...) 然后试图通过引用传参绕过——容易混淆所有权且不直观
如果根节点为空，直接返回新节点；否则递归后一定返回当前 root，保证上层能接住

迭代实现要注意指针的双重身份

迭代法不用函数调用栈，但得手动维护“当前节点”和“父节点”两个角色。常见错误是：只移动 cur，却没记住它从哪来，导致最后找不到地方挂新节点。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

必须用一个额外指针（比如 parent）记录上一个非空节点
循环中只负责导航，真正插入发生在循环结束后，靠 parent->left 或 parent->right 赋值
别在循环里直接 new，否则可能覆盖已有子树

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    TreeNode* cur = root;
    TreeNode* parent = nullptr;
    while (cur) {
        parent = cur;
        if (val val) cur = cur->left;
        else cur = cur->right;
    }
    if (val val) parent->left = new TreeNode(val);
    else parent->right = new TreeNode(val);
    return root;
}