C++ - 二叉搜索树讲解
二叉搜索树概念和定义
二叉搜索树是一个二叉树,其中每个节点的值都满足以下条件:
- 节点的左子树只包含小于当前节点值的节点。
- 节点的右子树只包含大于当前节点值的节点。
- 左右子树也必须是二叉搜索树。

二叉树搜索树性质
从上面的二叉搜索树定义中可以了解到, 二叉搜索树是有序的.
通过中序遍历, 会发现这是个有序的序列, 升序或降序 (自己决定)
二叉搜索树只支持增删查, 不支持该.
因为如果随意修改二叉搜索树节点的值, 那么就有可能会导致, 这棵树不再满足二叉搜索树的条件.

二叉搜索树的查找的时间复杂度:
最好情况: O(log n)
最坏情况: O(N)

当二叉搜索树是以上的情况时, 就变成了链表, 那么时间复杂度就是 O(N).
二叉搜索树中是不能出现相同元素的.
二叉搜索树模拟实现
创建一个二叉搜索树节点类
template<class T>
struct SearchTreeNode
{T _data; // 存储数据SearchTreeNode<T>* _leftchile; // 指向左孩子SearchTreeNode<T>* _rightchild; // 指向右孩子SearchTreeNode(const T& data):_data(data),_leftchile(nullptr),_rightchild(nullptr){}
};
二叉搜索树类创建
template<class T>
class SearchTree
{typedef SearchTreeNode<T> SearchTreeNode;
public:bool insert(const T& data){}bool erase(const T& data){}bool find(const T& data){}
private:SearchTreeNode* _root;
};
二叉搜索树的插入
二叉搜索树的插入非常简单.
从根节点开始, 如果插入的值小于节点值, 那么向左走,
如果插入的值大于节点值, 那么向右走,
如果值已存在, 那么直接返回 false.
bool insert(const T& data)
{SearchTreeNode* node = new SearchTreeNode(data);if (_root == nullptr) // 如果 _root 为空, 那么也就需要更新 _root 节点{_root = node;return true;}else{SearchTreeNode* prev = nullptr; // 记录插入位置的父节点SearchTreeNode* cur = _root; // 查找插入位置while (cur != nullptr){if (cur->_data == data) // 如果要插入的数据已存在, 直接返回{return false;}if (data < cur->_data) // 要插入的数据小于节点数据, 向左走{prev = cur;cur = cur->_leftchile;}else // 要插入的数据大于节点数据, 向右走{prev = cur;cur = cur->_rightchild;}}if (data < prev->_data) // 判断要插入的位置是左边还是右边{prev->_leftchile = node;}else{prev->_rightchild = node;}return true;}
}
二叉搜索树的删除
1. 被删除的节点最多只有一个孩子
1) 被删除的节点是叶子节点, 没有孩子
这种情况下, 直接将这个节点删除即可
2) 被删除的节点只有左孩子
将本节点删除后, 将节点的左孩子连接到本节点的父节点上

3) 被删除的节点只有右孩子
和只有左孩子相同, 删除本节点, 右孩子连接到本节点的父节点上

void erase(const T& data)
{SearchTreeNode* prev = nullptr;SearchTreeNode* cur = _root;while (cur != nullptr) // 先查找是否存在这个值{if (data == cur->_data){break;}prev = cur;if (data < cur->_data){cur = cur->_leftchile;}else{cur = cur->_rightchild;}}if (cur == nullptr) // 不存在这个值, 直接返回{return;}if (cur->_leftchile == nullptr || cur->_rightchild == nullptr) // 存在这个节点, 这个节点没有孩子, 或者只有一个孩子{if (cur->_leftchile == nullptr) // 只有右孩子{if (_root == cur) // 如果要删除的节点就是 _root, 更新 _root{_root = cur->_rightchild;}else{if (prev->_leftchile = cur) // 判断要连接再父节点的哪边{prev->_leftchile = cur->_rightchild;}else{prev->_rightchild = cur->_rightchild;}}}else{if (_root == cur){_root = cur->_leftchile;}else{if (prev->_leftchile = cur){prev->_leftchile = cur->_leftchile;}else{prev->_rightchild = cur->_leftchile;}}}delete cur;}
}
2. 被删除的节点有两个孩子
我们不直接删除这个节点, 使用和 堆 删除节点差不多的方法.
我们将要删除的这个节点和一个最多只有一个孩子的节点进行交换
然后删除那个交换后的值.
那么这个交换的节点怎么选择.
1. 本节点右子树中的最小值的那个节点 (即右子树的最左节点)
2. 本节点左子树中的最大值的那个节点 (左子树的最右节点)
这两个选择方法, 选择出来的要交换的节点的值, 都是最接近 本节点值的 节点.

找到这个节点之后, 交换 cur 和 child 的值, 然后删除 child 节点即可.
void erase(const T& data)
{SearchTreeNode* prev = nullptr;SearchTreeNode* cur = _root;while (cur != nullptr) // 先查找是否存在这个值{if (data == cur->_data){break;}prev = cur;if (data < cur->_data){cur = cur->_leftchile;}else{cur = cur->_rightchild;}}if (cur == nullptr) // 不存在这个值, 直接返回{return;}if (cur->_leftchile == nullptr || cur->_rightchild == nullptr) // 存在这个节点, 这个节点没有孩子, 或者只有一个孩子{if (cur->_leftchile == nullptr){if (_root == cur){_root = cur->_rightchild;}else{if (prev->_leftchile = cur){prev->_leftchile = cur->_rightchild;}else{prev->_rightchild = cur->_rightchild;}}}else{if (_root == cur){_root = cur->_leftchile;}else{if (prev->_leftchile = cur){prev->_leftchile = cur->_leftchile;}else{prev->_rightchild = cur->_leftchile;}}}delete cur;}else // 这个节点有两个孩子, 上半部分代码 和 文章上面的代码是一样的{prev = cur;SearchTreeNode* child = cur->_rightchild; // 要删除的节点while (child->_leftchile != nullptr) // 查找符合要求的节点{prev = child;child = child->_leftchile;}cur->_data = child->_data; // 交换数据if (child->_rightchild == nullptr) // child 是叶子节点{if (prev == cur) // 可以看下图演示{prev->_rightchild = nullptr;}else{prev->_leftchile = nullptr;}}else // child 有右子树, 这不可能有左子树, 因为这里找的就是最左节点{if (prev == cur){prev->_rightchild = cur->_rightchild;}else{prev->_leftchile = child->_rightchild;}}delete child;}
}

那么另一种方法, 和这种方法差不多, 会一种就会另一种.
去本节点左子树中, 查找最右的节点.
至于查找功能, 无论是再插入还是删除中, 都有这部分操作.
相关文章:
C++ - 二叉搜索树讲解
二叉搜索树概念和定义 二叉搜索树是一个二叉树,其中每个节点的值都满足以下条件: 节点的左子树只包含小于当前节点值的节点。节点的右子树只包含大于当前节点值的节点。左右子树也必须是二叉搜索树。 二叉树搜索树性质 从上面的二叉搜索树定义中可以了…...
基于开源云原生数据仓库 ByConity 体验多种数据分析场景
基于开源云原生数据仓库 ByConity 体验多种数据分析场景 业务背景什么是 ByConity上手实测环境要求测试操作远程登录 ECS 服务器windows10 自带连接工具 执行查询 ByConity 相对于 ELT 能力的优化提升并行度任务级重试并行写入简化数据链路 业务背景 大家都知道,在…...
RabbitMQ 消息确认机制
RabbitMQ 消息确认机制 本文总结了RabbitMQ消息发送过程中的一些代码片段,详细分析了回调函数和发布确认机制的实现,以提高消息传递的可靠性。 返回回调机制的代码分析 主要用途 这个代码主要用于设置RabbitMQ消息发送过程中的回调函数,即…...
Node.js:开发和生产之间的区别
Node.js 中的开发和生产没有区别,即,你无需应用任何特定设置即可使 Node.js 在生产配置中工作。但是,npm 注册表中的一些库会识别使用 NODE_ENV 变量并将其默认为 development 设置。始终在设置了 NODE_ENVproduction 的情况下运行 Node.js。…...
【QT】背景,安装和介绍
TOC 目录 背景 GUI技术 QT的安装 使用流程 QT程序介绍 main.cpp编辑 Wiget.h Widget.cpp form file .pro文件 临时文件 C作为一门比较古老的语言,在人们的认知里始终是以底层,复杂和高性能著称,所以在很多高性能需求的场景之下…...
从0到1搭建webpack
好,上一篇文章我们说了一下在react中怎么弄这个webpack,那么现在在说一下不用react我们又该怎么配置,这些呢也都是我自己通弄过看视频自己总结的,拿来给大家分享一下。 前期准备条件 1、nvm(可以快速切换node版本&am…...
针对解决conda环境BUG的个人笔记
1-conda学习&安装 安装视频: 零基础教程:基于Anaconda和PyCharm配置Pytorch环境_哔哩哔哩_bilibili 安装过程: MX250笔记本安装Pytorch、CUDA和cuDNN-CSDN博客 Win10MX250CUDA10.1cuDNNPytorch1.4安装测试全过程(吐血)_nvidia geforc…...
读《Effective Java》笔记 - 条目13
条目13:谨慎重写clone方法 浅拷贝和深拷贝 浅拷贝(Shallow Copy) 浅拷贝 只复制对象本身,而不复制对象引用的成员。 对于引用类型的字段,浅拷贝会将原对象的引用复制到新对象中,而不会创建新对象实例。因…...
SQL 之连接查询
SQL 连接查询:深入理解 JOIN 操作 在数据库管理中,连接查询(JOIN)是一种基本而强大的操作,它允许我们从两个或多个表中检索数据。SQL 中的 JOIN 操作使得数据整合变得简单,这对于数据分析和报告至关重要。…...
vscode切换anaconda虚拟环境解释器不成功
问题: 切换解释器之后运行代码还是使用的原来的解释器 可以看到,我已经切换了“nlp”解释器,我的nltk包只在“nlp”环境下安装了,但是运行代码依然是"torch"解释器,所以找不到“nltk”包。 在网上找了各种…...
一个实用的 Maven localRepository 工具
目录 1 现状2 当前解决3 更好的解决3.1 下载 Maven localRepository 工具包3.2 上传本地 localRepository 包3.3 清理 localRepository 中指定后缀的文件 1 现状 在使用 Maven 时,我们可能会经常与本地仓库和私服仓库打交道。 例如对于本地仓库,因为某…...
目标检测,图像分割,超分辨率重建
目标检测和图像分割 目标检测和图像分割是计算机视觉中的两个不同任务,它们的输出形式也有所不同。下面我将分别介绍这两个任务的输出。图像分割又可以分为:语义分割、实例分割、全景分割。 语义分割(Semantic Segmentation)&…...
微信小程序 城市点击后跳转 并首页显示被点击城市
在微信小程序中,渲染出城市列表后,如何点击城市,就跳转回到首页,并在首页显示所点击的城市呢? 目录 一、定义点击城市的事件 二、首页的处理 首页:点击成都市会跳转到城市列表 城市列表:点击…...
Linux - nfs服务器
五、nfs服务器 1、基础 NFS服务器可以让PC将网络中的NFS服务器共享的目录挂载到本地端的文件系统中,而在本地端的系统 中看来,那个远程主机的目录就好像是自己的一个磁盘分区一样。 由于NFS支持的功能比较多,而不同的功能都会使用不同的程…...
uniapp图片上传预览uni.chooseImage、uni.previewImage
文章目录 1.上传图片2.预览图片 1.上传图片 uni.chooseImage(OBJECT) 从本地相册选择图片或使用相机拍照。 App端如需要更丰富的相机拍照API(如直接调用前置摄像头),参考plus.camera 微信小程序从基础库 2.21.0 开始, wx.choos…...
C++ 字符串中数字识别
【问题描述】 输入一个字符串,含有数字和非数字字符,如“sumabc234;while(abc700)tab{ass346;bssabc267;}”,将其中连续的数字作为一个整数,依次存放到一个数组nums中。例如,234放在nums[0],700放在nums[1…...
学术中常见理论归纳总结-不定期更新
1.信息传播类 1.1 扩散创新理论 创新扩散理论是传播效果研究的经典理论之一,是由美国学者埃弗雷特罗杰斯(E.M.Rogers)于20世纪60年代提出的一个关于通过媒介劝服人们接受新观念、新事物、新产品的理论,侧重大众传播对社会和文化的影响。 1927-1941年进行的“艾奥瓦杂交玉…...
ModelSim怎么修改字体及大小
点击TOOLS 选择PERFERENCES选择下一级菜单的TEXTFONT/CHOOSE/选择字体和大小最后不要忘记点apply再退出...
图片预处理技术介绍4——降噪
图片预处理 大家好,我是阿赵。 这一篇将两种基础的降噪算法。 之前介绍过均值模糊和高斯模糊。如果从降噪的角度来说,模糊算法也算是降噪的一类,所以之前介绍的两种模糊可以称呼为均值降噪和高斯降噪。不过模糊算法对原来的图像特征的…...
Scrapy管道设置和数据保存
1.1 介绍部分: 文字提到常用的Web框架有Django和Flask,接下来将学习一个全球范围内流行的爬虫框架Scrapy。 1.2 内容部分: Scrapy的概念、作用和工作流程 Scrapy的入门使用 Scrapy构造并发送请求 Scrapy模拟登陆 Scrapy管道的使用 Scrapy中…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...
深度解析:etcd 在 Milvus 向量数据库中的关键作用
目录 🚀 深度解析:etcd 在 Milvus 向量数据库中的关键作用 💡 什么是 etcd? 🧠 Milvus 架构简介 📦 etcd 在 Milvus 中的核心作用 🔧 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...
