C++如何实现一个二叉搜索树？（数据结构代码）

admin 百科 2025-12-12 13

C++实现BST需定义节点结构，支持插入、查找、删除：插入递归比较值并挂载；查找用迭代法O(1)空间；删除分三类——无子节点直接删、单子节点替代、双子节点用右子树最小值替换并递归删该值。

C++如何实现一个二叉搜索树？（数据结构代码）-第1张图片-佛山资讯网

用C++实现二叉搜索树（BST），核心是定义节点结构、支持插入、查找、删除三种基本操作，并保证左子树所有节点值

节点定义与基础结构

每个节点包含数据、左指针、右指针。推荐用指针管理内存，配合构造函数简化初始化：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    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;
}

登录后复制

查找操作（迭代更简洁）

利用BST性质逐层向下，无需递归，空间复杂度O(1)：

标签： node c++

本文地址： https://www.fsgp.cn/p/baike/50777.html