当前位置： 首页 > news >正文

【C++进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫

news 2025/7/12 14:22:35

二叉树1：深入理解数据结构第一弹——二叉树（1）——堆-CSDN博客

二叉树2：深入理解数据结构第三弹——二叉树（3）——二叉树的基本结构与操作-CSDN博客

二叉树3：深入理解数据结构第三弹——二叉树（3）——二叉树的基本结构与操作-CSDN博客

前言：


在之前我们用C语言实现数据结构时，已经对二叉树进行了系统的学习，但还是有一些内容并没有涉及到，比如今天要讲的二叉搜索树，因为二叉搜索树在C++中有现成的模板库——set和map，并且实现起来较为麻烦，所以我们放到这里来讲，对前面二叉树部分有所遗忘的同学可以在我的主页搜一下之前的文章看一下

目录

一、二叉搜索树的概念

二、二叉搜索树的基本操作

1. 插入节点

2. 查找节点

3. 删除节点

三、二叉搜索树的实现

四、二叉搜索树的应用

五、总结

一、二叉搜索树的概念

二叉搜索树又称二叉排序树，它是一种具有特殊性质的二叉树，它具有以下特点：

1. 有序性：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而其右子树中的所有节点的值都大于该节点的值。

2. 唯一性：树中的每个节点的值都是唯一的，不存在重复的值。

3. 递归性：它的子树也都是二叉树

上面这三种性质，最不好理解的应该是有序性，下面我们通过两个例子来展现这三种性质：

二、二叉搜索树的基本操作

1. 插入节点

插入节点的过程如下：

  • 从根节点开始，比较要插入的值与当前节点的值。
  • 如果要插入的值小于当前节点的值，则移动到左子节点；如果要插入的值大于当前节点的值，则移动到右子节点。
  • 重复上述过程，直到找到一个空位置，然后在该位置插入新节点。
2. 查找节点

查找节点的过程如下：

  • 从根节点开始，比较要查找的值与当前节点的值。
  • 如果要查找的值等于当前节点的值，则返回该节点。
  • 如果要查找的值小于当前节点的值，则移动到左子节点；如果要查找的值大于当前节点的值，则移动到右子节点。
  • 重复上述过程，直到找到目标节点或遍历到空节点。
3. 删除节点

删除节点的过程相对复杂，需要考虑以下几种情况：

  • 删除叶子节点：直接删除该节点。
  • 删除只有一个子节点的节点：将其子节点替换到该节点的位置。
  • 删除有两个子节点的节点：找到该节点右子树中的最小节点（或左子树中的最大节点），将其值替换到该节点的位置，然后删除该最小节点。

三、二叉搜索树的实现

template<class T>
struct BSTNode
{BSTNode(const T& data = T()): _pLeft(nullptr) , _pRight(nullptr), _data(data){}BSTNode<T>* _pLeft;BSTNode<T>* _pRight;T _data;
};
template<class T>
class BSTree
{typedef BSTNode<T> Node;typedef Node* PNode;
public:BSTree(): _pRoot(nullptr){}// 自己实现，与二叉树的销毁类似~BSTree();// 根据二叉搜索树的性质查找：找到值为data的节点在二叉搜索树中的位置PNode Find(const T& data);bool Insert(const T& data){// 如果树为空，直接插入if (nullptr == _pRoot){_pRoot = new Node(data);return true;}// 按照二叉搜索树的性质查找data在树中的插入位置PNode pCur = _pRoot;// 记录pCur的双亲，因为新元素最终插入在pCur双亲左右孩子的位置PNode pParent = nullptr;while (pCur){pParent = pCur;if (data < pCur->_data)
比特就业课pCur = pCur->_pLeft;else if (data > pCur->_data)pCur = pCur->_pRight;  // 元素已经在树中存在elsereturn false;}// 插入元素pCur = new Node(data);if (data < pParent->_data)pParent->_pLeft = pCur;elsepParent->_pRight = pCur;return true;}bool Erase(const T& data){// 如果树为空，删除失败if (nullptr == _pRoot)return false;// 查找在data在树中的位置PNode pCur = _pRoot;PNode pParent = nullptr;while (pCur){if (data == pCur->_data)break;else if (data < pCur->_data){pParent = pCur;pCur = pCur->_pLeft;}else{pParent = pCur;pCur = pCur->_pRight;}}// data不在二叉搜索树中，无法删除if (nullptr == pCur)return false;// 分以下情况进行删除，同学们自己画图分析完成if (nullptr == pCur->_pRight){// 当前节点只有左孩子或者左孩子为空---可直接删除}else if (nullptr == pCur->_pRight){// 当前节点只有右孩子---可直接删除}else{
// 当前节点左右孩子都存在，直接删除不好删除，可以在其子树中找一个替代结点，
比如：// 找其左子树中的最大节点，即左子树中最右侧的节点，或者在其右子树中最小的节
点，即右子树中最小的节点// 替代节点找到后，将替代节点中的值交给待删除节点，转换成删除替代节点}return true;}
// 自己实现void InOrder();
private:PNode _pRoot;
};

四、二叉搜索树的应用

在我们目前的学习中，二叉搜索树最重要的用途就是key--val模型，KV模型就是每一个key值都对应一个val值，这样就形成一个<key,val>键值对，这样的应用在生活中是非常常见的

比如：在菜市场中不同的蔬菜对应着不同的价格；新华词典中，不同的汉字对应着不同的拼音，这些都可以用KV模型来解决

下面是KV模型的实现（没有主函数）：

namespace kv
{template<class K,class V>struct BSTreeNode{BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _value;BSTreeNode(const K& key,const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};template<class K,class V>class BSTree{typedef BSTreeNode<K,V> Node;public://遍历（中序）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;}///bool Insert(const K& key,const V& value){if (_root == nullptr){_root = new Node(key,value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return false;}}cur = new Node(key,value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{// 准备删除  20:15继续if (cur->_left == nullptr){//左为空if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){//右为空if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{//左右都不为空// 右树的最小节点(最左节点)Node* parent = cur;Node* subLeft = cur->_right;while (subLeft->_left){parent = subLeft;subLeft = subLeft->_left;}swap(cur->_key, subLeft->_key);if (subLeft == parent->_left)parent->_left = subLeft->_right;elseparent->_right = subLeft->_right;delete subLeft;}return true;}}return false;}BSTree() = default;~BSTree(){Destroy(_root);}//递归版本bool InsertR(const K& key){return _InsertR(_root, key);}bool FindR(const K& key){return _FindR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}BSTree(const BSTree<K,V>& t){_root = Copy(t._root);}BSTree<K,V>& operator=(BSTree<K,V> t){swap(_root, t._root);return *this;}private:Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_key);newroot->_left = Copy(root->_left);newroot->_right = Copy(root->_right);return newroot;}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{if (root->_left == nullptr){root = root->_right;return true;}else if (root->_right == nullptr){root = root->_left;return true;}else{Node* subLeft = root->_right;while (subLeft->_left){subLeft = subLeft->_left;}swap(root->_key, subLeft->_key);return _EraseR(root->_right, key);}}}bool _FindR(Node* root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return root->_right;}else if (root->_key > key){return root->_left;}else{return true;}}bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}Node* _root = nullptr;};
}

五、总结

以上就是二叉搜索树的主要内容，在代码实现上其实与之前讲的二叉树差别并不是很大，关键在于思路的梳理，这章就先到这了

感谢各位大佬观看，创作不易，还请各位大佬点赞支持！！！

http://www.lryc.cn/news/389641.html

相关文章：

  • 【RabbitMQ实战】Springboot 整合RabbitMQ组件，多种编码示例，带你实践 看完这一篇就够了
  • 【你也能从零基础学会网站开发】理解DBMS数据库管理系统架构,从用户到数据到底经历了什么
  • Vue.js 中的API接口封装实战与详解
  • 职场内卷、不稳定、没前景……怎么破？
  • LeetCode 算法：将有序数组转换为二叉搜索树 c++
  • 智慧公厕系统改变了人们对服务区公厕的看法
  • 终极指南：RNNS、Transformers 和 Diffusion 模型
  • WPF UI 3D 基本概念 点线三角面 相机对象 材质对象与贴图 3D地球 光源 变形处理 动作交互 辅助交互插件 系列三
  • 分子AI预测赛Task2笔记
  • 剖析DeFi交易产品之UniswapV4：创建池子
  • 速盾：cdn内容分发服务有哪些优势？
  • 如何利用React和Python构建强大的网络爬虫应用
  • 炎黄数智人：招商局集团推出AI数字员工“招小影”
  • 【开发篇】明明配置跨域声明，为什么却仍可以发送HTTP请求
  • 单片机中有FLASH为啥还需要EEROM？
  • Qt的源码目录集合(V5.12.12版本)
  • 记因hive配置文件参数运用不当导致 sqoop MySQL导入数据到hive 失败的案例
  • 自动化邮件通知：批处理脚本的通讯增强
  • 236、二叉树的最近公共祖先
  • WebStorm 2024 for Mac JavaScript前端开发工具
  • 【Redis7】零基础篇
  • [ROS 系列学习教程] 建模与仿真 - 使用 ros_control 控制差速轮式机器人
  • Ubuntu22.04使用Systemd设置ROS 2开机自启动遇到的问题
  • AI安全研究滞后？清华专家团来支招
  • 12寸FAB 信息部内外工作职责的一些划分构思
  • css做旋转星球可举一反三
  • AcWing 1256：扩展二叉树
  • 三维家：SaaS的IT规模化降本之道｜OceanBase 《DB大咖说》（十一）
  • ai智能语音机器人是如何影响客户体验的?电销机器人部署
  • vue3使用v-html实现文本关键词变色