c++中如何在二叉搜索树插入节点_c++二叉搜索树插入节点方法-C++-PHP中文网

c++中如何在二叉搜索树插入节点_c++二叉搜索树插入节点方法

尼克

发布： 2025-10-02 22:02:02

原创

607人浏览过

插入节点需遵循BST规则，递归法通过比较值大小决定左右子树插入位置，代码简洁；迭代法用指针遍历至空位插入，节省栈空间。两种方法均保持BST性质，中序遍历结果有序，可根据场景选择使用。

c++中如何在二叉搜索树插入节点_c++二叉搜索树插入节点方法

在C++中，向二叉搜索树（Binary Search Tree, BST）插入节点需要遵循BST的规则：对于任意节点，左子树的所有值小于该节点值，右子树的所有值大于该节点值。插入操作可以通过递归或迭代方式实现。

定义二叉搜索树节点结构

插入前，先定义树的节点结构：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

登录后复制

递归方式插入节点

递归方法思路清晰，从根节点开始比较，根据值的大小决定进入左子树或右子树，直到找到空位置插入新节点。

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; // 返回根节点
}

登录后复制

说明：函数返回类型为 TreeNode*，用于更新子树连接。若根为空，直接返回新节点；否则递归处理左右子树。

立即学习“C++免费学习笔记（深入）”；

迭代方式插入节点

迭代方式使用指针遍历树，找到合适的空位置后插入，无需递归调用。

MindShow

MindShow官网 | AI生成PPT，快速演示你的想法

1492

查看详情

TreeNode* insertIntoBST(TreeNode* root, int val) {
    TreeNode* newNode = new TreeNode(val);
    if (!root) return newNode;
<pre class='brush:php;toolbar:false;'>TreeNode* current = root;
while (true) {
    if (val < current->val) {
        if (!current->left) {
            current->left = newNode;
            break;
        }
        current = current->left;
    } else {
        if (!current->right) {
            current->right = newNode;
            break;
        }
        current = current->right;
    }
}
return root;

登录后复制

}

说明：从根节点开始移动指针，根据比较结果向左或向右走，直到子节点为空时插入新节点。

使用示例

构建一个简单BST并插入节点：

int main() {
    TreeNode* root = nullptr;
    root = insertIntoBST(root, 5);
    root = insertIntoBST(root, 3);
    root = insertIntoBST(root, 7);
    root = insertIntoBST(root, 2);
    root = insertIntoBST(root, 4);
    return 0;
}

登录后复制

最终形成的树结构符合BST性质，中序遍历会输出有序序列：2, 3, 4, 5, 7。

基本上就这些。递归写法简洁，适合理解逻辑；迭代节省栈空间，适合深度较大的树。根据需求选择合适方法即可。

以上就是c++++中如何在二叉搜索树插入节点_c++二叉搜索树插入节点方法的详细内容，更多请关注php中文网其它相关文章！