C++二叉搜索树

2401_87151858

366人浏览 · 2025-10-25 17:23:28

2401_87151858 · 2025-10-25 17:23:28 发布

注：本文所介绍的二叉搜索树不包含重复元素

二叉搜索树：对任意节点x，其左子树的所有节点的权值都小于x节点的权值；其右子树的所有节点的权值都大于x节点的权值。

二叉搜索树示例图：
在这里插入图片描述

二叉搜索树的性质：中序遍历是有序的（按权值从小到大的顺序）

二叉搜索树节点定义

// 节点
template<class K>
struct BSTree_node
{
    K _key;	// 权值
    BSTree_node* _left;	// 左儿子
    BSTree_node* _right;// 右儿子
    BSTree_node(const K& key, BSTree_node* left = nullptr, BSTree_node* right = nullptr)
        :_key(ket)
        ,_left(left)
        ,_right(right)
    {}
};

// 二叉搜索树
template<class K>
class BSTree
{
    typedef BSTree_node<K> node;
    node* _root = nullptr; // 注意这里给了缺省值
};

二叉搜索树的查找

在以root为跟节点的二叉搜索树中查找权值为x的节点

root为空，返回nullptr
若x小于root节点的权值，就去root的左子树查找
若x大于root节点的权值，就去root的右子树查找
若x等于root节点的权值，返回root

例如在上述示例图中查找15

在这里插入图片描述

代码如下

template<class K>
class BSTree
{
    typedef BSTree_node<K> node;
    node* _root;
public:
    node* find(const K& x)
    {
        node* root = _root;
        while(root)
        {
            if(x < root->_key) root = root->_left;
            else if(x > root->_key) root = root->_right;
            else break;
        }
        return root
    }
};

二叉搜索树的插入

在以root为跟节点的二叉搜索树中插入权值为x的节点（root的父节点为p，_root的父节点为nullptr）

root为空
- 若p也为空，则整棵树为空，新建一个节点，将其赋值给根节点(_root)
- 若x小于p的权值，则将新节点插入为p的左儿子节点。
- 若x大于p的权值，则将新节点插入为p的右儿子节点。
若x小于root节点的权值，就去root的左子树插入
若x大于root节点的权值，就去root的右子树插入
若x等于root节点的权值，返回false

在这里插入图片描述

代码如下

    // 成功插入返回true，否则返回false
    bool insert(const K& x)
    {
        if(!_root)
        {
            _root = new node(x);
            return true;
        }
        node* root = _root;
        node* p = nullptr;
        while(root)
        {
            p = root;
            if(x < root->_key) root = root->_left;
            else if(x > root->_key) root = root->_right;
            else return false;
        }
        if(x < p->_key) p->_left = new node(x);
        else p->_right = new node(x);
        return true;
    }

补充：中序遍历打印代码

    void _print(node* root)
    {
        if(!root) return;
        _print(root->_left);
        cout << root->_key << ' ';
        _print(root->_right);
    }
    void print()
    {
        _print(_root);
        cout << endl;
    }

测试

int main()
{
    BSTree<int> t;
    int a[] = {12, 4, 17, 0, 1, 1, 5, 15, 16};
    for(auto e : a)
        t.insert(e);
    
    t.print();
    return 0;
}

运行结果
在这里插入图片描述

二叉搜索树的删除

在以root为跟节点的二叉搜索树中删除权值为x的节点

情况1：root的左右儿子都没有，直接删除
在这里插入图片描述

情况2：root只有一个儿子，将该儿子提升至root位置，并修改其父节点，用root的儿子代替root

在这里插入图片描述

情况3：root有两个儿子，用root的前驱pre替代root（前驱：root的左子树的最大值），即：交换pre与root的值，再删除pre(删除pre一定会满足情况1或者情况2)
当然也可以用root的后继替代（后继：root的右子树的最小值）

在这里插入图片描述

删除操作的代码如下：

    // 成功删除返回true，否则返回false
    bool erase(const K& x)
    {
        node* root = _root;
        node* p = nullptr;
        while(root)
        {
            if(x < root->_key) 
                p = root, root = root->_left;
            else if(x > root->_key) 
                p = root, root = root->_right;
            else{
                // 删除
                // 情况1，root为叶子节点
                if(!root->_left && !root->_right)
                {
                    if(!p) _root = nullptr; // 需要特判一下树中只有一个节点的情况
                    else if(root == p->_left) p->_left = nullptr;
                    else p->_right = nullptr;
                    delete root;
                    return true;
                }

                // 情况2，root只有一个儿子
                else if(!root->_left || !root->_right)
                {
                    node* child = root->_left ? root->_left : root->_right;
                    // 特判树根就是root的情况
                    if(!p)  _root = child;
                    else if(root == p->_left) p->_left = child;
                    else p->_right = child;
                    delete root;
                    return true;
                }

                // 情况3，root有两个儿子
                else{
                    // 找前驱
                    node* pre = root->_left;
                    node* pre_parent = root;
                    while(pre->_right) 
                    {
                        pre_parent = pre;
                        pre = pre->_right;
                    }
                    // 到这里，pre必定没有右儿子
                    root->_key = pre->_key;
                    if(pre_parent->_left == pre) pre_parent->_left = pre->_left;
                    else pre_parent->_right = pre->_left;
                    delete pre;
                    return true;
                }
            }
        }
        return false;
    }

构造

    // 无参构造，这里无需写_root = nullptr; 因为我已经给了缺省值
    BSTree() {}

    // 迭代器区间构造
    template<class InputIterator>
    BSTree(InputIterator first, InputIterator last) 
    {
        while(first != last)
        {
            insert(*first);
            ++first;
        }
    }

测试

void test01()
{
    int a[10] = {12, 4, 17, 0, 1, 1, 5, 15, 16, 4};
    BSTree<int> t;
    BSTree<int> t1(a, a + 10);  // 迭代器构造
    t.print();
    t1.print();
}

运行结果
在这里插入图片描述

析构

在此之前先写一个clear函数

    void clear() 
    { 
        _clear(_root); // _clear去释放空间
        _root = nullptr;	// 置空
    }

	// 后序遍历释放空间
    void _clear(node* root)
    {
        if(!root) return;
        _clear(root->_left);
        _clear(root->_right);
        delete root;
    }
    
    // 析构函数直接调用clear即可
    ~BSTree()  { clear(); }

拷贝构造

如可拷贝一颗树呢？
答：拷贝左子树、拷贝右子树，再拷贝根节点，最后连接起来

    node* copy(node* root)
    {
        if(!root) return nullptr;
        node* left = copy(root->_left);     // 拷贝左子树
        node* right = copy(root->_right);   // 拷贝右子树
        node* r = new node(root->_key);     // 拷贝root
        r->_left = left, r->_right = right; // 连接起来
        return r;
    }
    
    // 拷贝构造直接调用copy即可
    BSTree(const BSTree& t) { _root = copy(t._root); }

赋值重载

这部分套路与之前讲的STL内容类似，用拷贝构造配合swap即可

	// 交换两棵树
    void swap(BSTree& t)
    {
        std::swap(_root, t._root);
    }
    BSTree& operator= (const BSTree& t)
    {
        if(this != &t)
        {
            BSTree tmp(t);
            swap(tmp); 
            // tmp出作用域会自动销毁
        }
        return *this;
    }

结尾

补充：
若想支持插入重复元素呢？只需在节点定义中添加一个计数变量

template<class K>
struct BSTree_node
{
    K _key;	// 权值
    int _cnt;	// 记录权值为_key的数量
    BSTree_node* _left;	// 左儿子
    BSTree_node* _right;// 右儿子
    BSTree_node(const K& key, BSTree_node* left = nullptr, BSTree_node* right = nullptr)
        :_key(ket)
        ,_left(left)
        ,_right(right)
    {}
};

然后再把插入与删除操作略作改动
插入操作：若找到重复元素，此节点为x，只需x->_cnt++即可
删除操作：找到待删除的元素，此节点为x，将x->_cnt--，然后若x->cnt == 0，再按那三种情况删除
（这部分读者可自行实现）

二叉搜索树的各种操作的效率与其高度有关，极端情况下会退化成单只链，为此我们需要将二叉搜索树变得平衡一点，至于如何保持平衡，且听下回分析！

以上就是本篇内容了，附上源码

template<class K>
struct BSTree_node
{
    K _key;
    BSTree_node* _left;
    BSTree_node* _right;
    BSTree_node(const K& key, BSTree_node* left = nullptr, BSTree_node* right = nullptr)
        :_key(key)
        ,_left(left)
        ,_right(right)
    {}
};

template<class K>
class BSTree
{
    typedef BSTree_node<K> node;
    node* _root = nullptr;

    void _print(node* root)
    {
        if(!root) return;
        _print(root->_left);
        cout << root->_key << ' ';
        _print(root->_right);
    }
    void _clear(node* root)
    {
        if(!root) return;
        _clear(root->_left);
        _clear(root->_right);
        delete root;
    }
    node* copy(node* root)
    {
        if(!root) return nullptr;
        node* left = copy(root->_left);     // 拷贝左子树
        node* right = copy(root->_right);   // 拷贝右子树
        node* r = new node(root->_key);     // 拷贝root
        r->_left = left, r->_right = right; // 连接起来
        return r;
    }
public:
    // 无参构造，这里无需写_root = nullptr; 因为我已经给了缺省值
    BSTree() {}

    // 迭代器区间构造
    template<class InputIterator>
    BSTree(InputIterator first, InputIterator last) 
    {
        while(first != last)
        {
            insert(*first);
            ++first;
        }
    }

    ~BSTree()  { 
        clear(); 
        cout << "~BSTree()" << endl;
    }
    void clear() 
    { 
        _clear(_root); 
        _root = nullptr;
    }
    BSTree(const BSTree& t) { _root = copy(t._root); }
    void swap(BSTree& t)
    {
        std::swap(_root, t._root);
    }
    BSTree& operator= (const BSTree& t)
    {
        if(this != &t)
        {
            BSTree tmp(t);
            swap(tmp);
        }
        return *this;
    }

    node* find(const K& x)
    {
        node* root = _root;
        while(root)
        {
            if(x < root->_key) root = root->_left;
            else if(x > root->_key) root = root->_right;
            else break;
        }
        return root;
    }

    // 成功插入返回true，否则返回false
    bool insert(const K& x)
    {
        if(!_root)
        {
            _root = new node(x);
            return true;
        }
        node* root = _root;
        node* p = nullptr;
        while(root)
        {
            p = root;
            if(x < root->_key) root = root->_left;
            else if(x > root->_key) root = root->_right;
            else return false;
        }
        if(x < p->_key) p->_left = new node(x);
        else p->_right = new node(x);
        return true;
    }

    // 成功删除返回true，否则返回false
    bool erase(const K& x)
    {
        node* root = _root;
        node* p = nullptr;
        while(root)
        {
            if(x < root->_key) 
                p = root, root = root->_left;
            else if(x > root->_key) 
                p = root, root = root->_right;
            else{
                // 删除
                // 情况1，root为叶子节点
                if(!root->_left && !root->_right)
                {
                    if(!p) _root = nullptr; // 需要特判一下树中只有一个节点的情况
                    else if(root == p->_left) p->_left = nullptr;
                    else p->_right = nullptr;
                    delete root;
                    return true;
                }

                // 情况2，root只有一个儿子
                else if(!root->_left || !root->_right)
                {
                    node* child = root->_left ? root->_left : root->_right;

                    if(!p)  // 特判树根就是root的情况
                        _root = _root->_left ? _root->_left : _root->_right;
                    else if(root == p->_left) p->_left = child;
                    else p->_right = child;
                    delete root;
                    return true;
                }

                // 情况3，root有l两个儿子
                else{
                    // 找前驱
                    node* pre = root->_left;
                    node* pre_parent = root;
                    while(pre->_right) 
                    {
                        pre_parent = pre;
                        pre = pre->_right;
                    }
                    // 到这里，pre必定没有右儿子
                    root->_key = pre->_key;
                    if(pre_parent->_left == pre) pre_parent->_left = pre->_left;
                    else pre_parent->_right = pre->_left;
                    delete pre;
                    return true;
                }
            }
        }
        return false;
    }

    void print()
    {
        _print(_root);
        cout << endl;
    }
};

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

2026企业微信AI Agent实测：7款技术方案对比

会话审计、敏感词管理、聊天质检、敏感行为识别、舆情、属性、词频及竞品分析覆盖服务风险；线索公海、客户、产品、商机、订单、回款、发票和业绩目标则连接销售全过程。快创助手负责快速建运营任务，策略生成把目标拆成方案，智能客服回答系统使用咨询，数据报表处理自然语言查数，AI洞察联合标签、订单和会话分析客户。我们设计了客户筛选、订单关联、销售交接、会话质检和异常恢复任务，配合技术访谈与行业公开资料复核。准备