欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

【C++】二叉搜索树

2026-10-25 分类：服务器技术 阅读(3) 评论(0)

目录

1. 二叉树定义

2. 二叉搜索树定义

2.1 定义：

2.2  二叉搜索树的优缺点：

3. 二叉搜索树代码模拟实现：

3.1 二叉搜索树的插入

3.2 二叉搜索树的查找

3.3 二叉搜索树的删除

3.4 二叉搜索树的模拟实现

4. 二叉搜索树的应用场景

1. 二叉树定义

【C 数据结构】 树 二叉树 堆 （堆的模拟实现篇）-CSDN博客

二叉树（Binary Tree）是树形结构的一种，指每个节点最多有两个子节点的树。这两个子节点通常分别称为左子树和右子树，且左右次序不能随意颠倒。

一棵二叉树通常满足以下特征：

  • 每个节点最多有两个子节点，即节点的度不超过 2。
  • 左子树和右子树是有序的，交换后属于不同的二叉树。
  • 即使某个节点只有一个子节点，也需要明确它是左子节点还是右子节点。
  • 二叉树可以为空，即不含任何节点。

从递归角度看，二叉树可以这样定义：一棵二叉树要么是空树，要么由根节点、一棵左子树和一棵右子树组成，且左子树和右子树本身也都是二叉树。

与普通树相比，二叉树的关键区别在于子节点数量受限且左右有序，这一特性使得二叉树在存储、遍历和查找等场景中更容易实现和分析。

2. 二叉搜索树定义

2.1 定义：

在某一个节点上的数值，一定比该节点的左子树大，比右子树小，不存在等于的情况。由中序遍历下，达到一个有序的排列。例如：该二叉树的底层是以<int>类型为主的二叉树，那么在某一个节点上，节点数值为8，那么左子树的所有数值一定小于8，右子树的所有数值一定大于8。

二叉搜索树展示图 2.1

2.2  二叉搜索树的优缺点：

优点：

  • 如果二叉搜索树在完全二叉树的情况下查询效率确实可以做到O（logN)的时间效率，查询速度也是非常快。

    • 缺点：

  • 如果二叉搜索树在非完全二叉树的情况，或者更加极端的单边情况的下，那么可能搜索的时间效率可能大大折扣，逼近O（N）的时间效率。
  • 二叉树没办法像 vector 一样随机数值。
  • 树的形态受插入顺序影响极大，形态不稳定。

    • 单边极端情况 2.2

    3. 二叉搜索树代码模拟实现：

    3.1 二叉搜索树的插入

    基于概念进行设计函数功能即可，注意点:

  • 重复插入相同内容是不可行的；
  • 插入方式要严格按照二叉搜索树的原理进行插入，如果二叉树内的节点内容存在一个或者多个都已模板class K 的 类型定义成员变量 _key 为比较基准；
  • 二叉树有两部分构成，一个struct 结构体的 BSTreeNode 节点，和二叉树class 类 BSTree 二叉树；

    • 代码判断：

  • 为空树，root 构建节点，之后构造节点由root 往左右节点衍生节点 。
  • 不为空树树，由 ket 比较，大于小于比较各个节点直到遇到空指针并申请空间构建节点。
  • 如果已存在相同节点就不可构建新的节点，判断节点构建失败，返回 false（构建节点成功就返回 true ）

    • 二叉树插入展示图3.1

    int arr[] = {5,3,7,1,4,2,0,6,8,9};
    // 插入
    bool Insert(const K& key, const V& value)
    {
    // 判断是否为空树
    if (_root == nullptr)
    {
    _root = new Node(key, value);
    return true;
    }
    else // 不为空树
    {
    // cur 记录上一步位置，dest 确定下一步位置
    Node* dest = _root, *cur = nullptr;
    while (dest)
    {
    // 比较找好 ket 的合适位置
    if (key < dest->_key)
    {
    cur = dest;
    dest = dest->_left;
    }
    else if (dest->_key < key)
    {
    cur = dest;
    dest = dest->_right;
    }
    else // 存在相同 ket 不构建节点
    {
    return false;
    }
    }
    dest = new Node(key, value);// 构造新节点
    if (key < cur->_key)
    {
    cur->_left = dest;
    }
    else if (cur->_key < key)
    {
    cur->_right = dest;
    }
    return true;
    }
    }

    3.2 二叉搜索树的查找

    代码判断标准：

  • key 依次比较，如果key == root->_key 就说明找到，返回对应位置
  • 找不就返回 nullptr 空指针

    • 查找二叉树展示图3.2

    // 查找 key
    Node* Find(const K& key)
    {
    Node* root = _root;
    while (root)
    {
    if (root->_key == key)
    {
    return root;
    }
    else if (root->_key < key)
    {
    root = root->_right;
    }
    else if (root->_key > key)
    {
    root = root->_left;
    }
    }
    return nullptr;
    }

    3.3 二叉搜索树的删除

    删除与其他功能相对比较复杂，如果只是单纯用查找函数的话，会到导致一个跟这个子节点的父亲节点找不到，所以目前 Find() 函数功能并不适合来用与查找想要删除节点，或者我们可以来实现一个Node* _Find(const &K ,Node*& cur )函数功能可以返回还是地址，并且 cur  的也可以找到对应的父亲节点。

    如何删除：

    二叉树的要被删除的节点可能分为4中情况，单独删掉该节点都有可能影响整个二叉搜索树的合理性，所以就会去找与他比较相似的数值代替位置，例如 要删除8，那么就会去找左右节点中最大最小的数代替，两种各选其一，但不是什么情况都是两者都可以，例如只有左子树，那么就只能去找左子树最大的数值，右子树同理，找最小的数值。

    删除示例图3.3

    如果删除的节点为子节点（没有左右子树） 直接删除
    如果删除的节点只有右子树 找右子树的最小数值
    如果删除的节点只有左子树 找左子树的最大数值
    如果删除的节点左右子树 找左右子树的最大最小都可以

    bool Erase(const K& key)
    {
    Node* root = _root, *cur = nullptr;//cur 预防找到 root 的位置为子节点
    // find
    while (root)
    {
    if (root->_key == key)
    {
    break;
    }
    else if (root->_key < key)
    {
    cur = root;
    root = root->_right;
    }
    else if (root->_key > key)
    {
    cur = root;
    root = root->_left;
    }
    }
    // 找不到
    if (root == nullptr)
    {
    return false;
    }
    // root 为子节点
    if (root->_left == nullptr && root->_right == nullptr)
    {
    // root 是 cur 的左子树
    if (cur == nullptr)
    {
    // root == _root 整个二叉搜索树就只有一个节点，并且要找到删除的数值就是 _root
    }
    else if (cur->_left == root)
    {
    cur->_left = nullptr;
    }
    else if(cur ->_right == root)
    {
    cur->_right = nullptr;
    }
    delete root;
    }
    // root 只有左子树
    else if (root->_right == nullptr)
    {
    Node* LeftMax = root->_left;
    cur = root;
    // cur LeftMax
    while (LeftMax->_right)
    {
    cur = LeftMax;
    LeftMax = LeftMax->_right;
    }
    if (LeftMax->_left != nullptr)
    {
    cur->_right = LeftMax->_left;
    }
    else
    {
    cur->_right = nullptr;
    }
    swap(LeftMax->_key, root->_key);
    swap(LeftMax->_value, root->_value);
    delete LeftMax;
    }
    else
    {
    // root 只有右子树
    // root 左右子树的情况
    Node* RightMin = root->_right;
    cur = root;
    // cur LeftMax
    while (RightMin->_left)
    {
    cur = RightMin;
    RightMin = RightMin->_left;
    }
    if (RightMin->_right != nullptr)
    {
    cur->_left = RightMin->_right;
    }
    else
    {
    cur->_left = nullptr;
    }
    swap(RightMin->_key, root->_key);
    swap(RightMin->_value, root->_value);
    delete RightMin;
    }
    return true;
    }

    3.4 二叉搜索树的模拟实现

    26_10_24 BSTree/BSTree.h · 浪子·悠仁/C++ 知识库 – 码云 – 开源中国

    #pragma once
    #include <string>
    #include <assert.h>
    #include <iostream>
    using namespace std;
    // K -> key V->talue
    template<class K ,class V>
    struct BSTreeNode
    {
    K _key;// 二叉搜索树的比较关键
    V _value;// 二叉搜索树的附加节点对象
    BSTreeNode<K,V>* _left;// 左子树
    BSTreeNode<K,V>* _right;// 右子树
    // 节点初始化
    BSTreeNode(const K& key,const V& value)
    {
    _key = key;
    _value = value;
    _left = _right = nullptr;
    }
    };
    template<class K, class V>
    class BSTree
    {
    typedef BSTreeNode<K, V> Node;
    public:
    // 插入
    bool Insert(const K& key, const V& value)
    {
    if (_root == nullptr)
    {
    _root = new Node(key, value);
    return true;
    }
    else
    {
    Node* dest = _root, *cur = nullptr;
    while (dest)
    {
    if (key < dest->_key)
    {
    cur = dest;
    dest = dest->_left;
    }
    else if (dest->_key < key)
    {
    cur = dest;
    dest = dest->_right;
    }
    else
    {
    return false;
    }
    }
    dest = new Node(key, value);
    if (key < cur->_key)
    {
    cur->_left = dest;
    }
    else if (cur->_key < key)
    {
    cur->_right = dest;
    }
    return true;
    }
    }
    // 查找 key
    Node* Find(const K& key)
    {
    Node* root = _root;
    while (root)
    {
    if (root->_key == key)
    {
    return root;
    }
    else if (root->_key < key)
    {
    root = root->_right;
    }
    else if (root->_key > key)
    {
    root = root->_left;
    }
    }
    return nullptr;
    }
    bool Erase(const K& key)
    {
    Node* root = _root, *cur = nullptr;//cur 预防找到 root 的位置为子节点
    // find
    while (root)
    {
    if (root->_key == key)
    {
    break;
    }
    else if (root->_key < key)
    {
    cur = root;
    root = root->_right;
    }
    else if (root->_key > key)
    {
    cur = root;
    root = root->_left;
    }
    }
    // 找不到
    if (root == nullptr)
    {
    return false;
    }
    // root 为子节点
    if (root->_left == nullptr && root->_right == nullptr)
    {
    // root 是 cur 的左子树
    if (cur == nullptr)
    {
    // root == _root 整个二叉搜索树就只有一个节点，并且要找到删除的数值就是 _root
    }
    else if (cur->_left == root)
    {
    cur->_left = nullptr;
    }
    else if(cur ->_right == root)
    {
    cur->_right = nullptr;
    }
    delete root;
    }
    // root 只有左子树
    else if (root->_right == nullptr)
    {
    Node* LeftMax = root->_left;
    cur = root;
    // cur LeftMax
    while (LeftMax->_right)
    {
    cur = LeftMax;
    LeftMax = LeftMax->_right;
    }
    if (LeftMax->_left != nullptr)
    {
    cur->_right = LeftMax->_left;
    }
    else
    {
    cur->_right = nullptr;
    }
    swap(LeftMax->_key, root->_key);
    swap(LeftMax->_value, root->_value);
    delete LeftMax;
    }
    else
    {
    // root 只有右子树
    // root 左右子树的情况
    Node* RightMin = root->_right;
    cur = root;
    // cur LeftMax
    while (RightMin->_left)
    {
    cur = RightMin;
    RightMin = RightMin->_left;
    }
    if (RightMin->_right != nullptr)
    {
    cur->_left = RightMin->_right;
    }
    else
    {
    cur->_left = nullptr;
    }
    swap(RightMin->_key, root->_key);
    swap(RightMin->_value, root->_value);
    delete RightMin;
    }
    return true;
    }
    void _InOrder(Node* root)
    {
    if (root == nullptr)
    {
    return;
    }
    _InOrder(root->_left);
    cout << root->_key << ":" << root->_value << endl;
    _InOrder(root->_right);
    }
    void InOrder()
    {
    _InOrder(_root);
    cout << endl;
    }
    private:
    Node* _root = nullptr;
    };

    4. 二叉搜索树的应用场景

    核心特点：中序遍历有序、支持动态插入 / 删除 / 查找、方便范围查询；工程里大多用它的平衡变种（红黑树、AVL 树），普通 BST 一般用于教学、小规模数据。

  • 编译器符号表 编译器用它保存变量名、函数名、类型、作用域，编译时快速查找标识符，C 语言早期符号表常用 BST 实现。
  • 有序关联容器底层 C++ std::map / std::set、Java TreeMap / TreeSet 底层是红黑树（自平衡 BST），可以维持 key 有序，支持按顺序遍历、找上下界、区间查询。
  • 数据库索引（扩展变种） MySQL InnoDB 索引是 B + 树（多路平衡搜索树，BST 的拓展），用来快速定位记录、范围查询，避免全表扫描；普通 BST 很少直接用于磁盘索引（树太高）。
  • 动态有序集合管理 需要频繁增删，同时要保持有序：排行榜、在线名单、权限白名单、词频统计、拼写检查词典。中序遍历就能直接拿到有序结果。
  • 文件系统目录 / 名字检索 按文件名、时间戳排序检索，动态新增、删除文件条目。
  • 离散化、区间问题、算法题 数据结构考题、OJ 题目：求前驱后继、统计区间元素数量、动态维护有序序列。
  • 自动补全、词典检索 单词词典，按字典序存储，输入前缀快速检索候选词。

    • void TestBSTree()
    {
    //单词查询
    BSTree<string, string> dict;
    dict.Insert("insert", "插入");
    dict.Insert("erase", "删除");
    dict.Insert("left", "左边");
    dict.Insert("string", "字符串");

    string str;
    while (cin >> str)
    {
    auto ret = dict.Find(str);
    if (ret)
    {
    cout << str << ":" << ret->_value << endl;
    }
    else
    {
    cout << "单词拼写错误" << endl;
    }
    }
    // 计算存在水果种类和各个水果数量
    string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
    // 统计水果出现的次
    BSTree<string, int> countTree;
    for (auto str : strs)
    {
    auto ret = countTree.Find(str);
    if (ret == NULL)
    {
    countTree.Insert(str, 1);
    }
    else
    {
    ret->_value++;
    }
    }
    countTree.InOrder();
    }

    感谢观看！

                                                                                                                                               悠仁さん

    赞(0)
    未经允许不得转载：171主机测评 » 【C++】二叉搜索树
    分享到： 更多 (0)
    标签：

    相关推荐

    评论 抢沙发

    取消

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址

    热门标签

    #人工智能(63708)#python(21287)#开发语言(17715)#java(16275)#运维(16072)#linux(15567)#大数据(15223)#服务器(13587)#算法(12233)#前端(11564)#ai(10102)#网络(9842)#数据库(9437)#c++(8598)#学习(7126)#课程设计(7007)#机器学习(6974)#区块链(6044)#后端(5500)#OpenClaw(5409)#spring boot(5262)#深度学习(5232)#c语言(4537)#安全(4456)#毕业设计(4391)#数据结构(4326)#架构(4137)#docker(4094)#javascript(3956)#大模型(3880)

    热门文章

    最新文章

    归档

    分类