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

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

裘德小鎮的故事

发布： 2025-09-27 18:18:02

原创

508人浏览过

首先定义二叉搜索树节点结构，包含值、左子节点和右子节点指针；递归插入时比较值大小，找到空位创建新节点并返回根；迭代法用指针遍历至合适位置后插入，避免栈开销；两种方法均保持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*，便于更新子树连接：

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

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

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* 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结构。递归写法简洁易懂，迭代更节省栈空间。选择哪种取决于具体需求和偏好。基本上就这些，不复杂但容易忽略边界情况，比如空树处理。

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