[C++]二叉搜索树

news/2024/4/17 11:33:37

一、定义

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

二、插入insert

对于二叉搜索树的插入操作,我们将需要插入的key值与当前结点(初始结点是root结点)比较,若小于该结点的值,则往左子树走;若大于该结点的值,则往右子树走。走到空结点的时候,那么这个位置就是这个key值的归宿。

template<class K, class V>
struct BSTreeNode
{BSTreeNode<K, V>* left;BSTreeNode<K, V>* right;K _key;V _value;
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public:BSTree(){_root = nullptr;}bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node;_root->_key = key;_root->_value = value;_root->left = nullptr;_root->right = nullptr;}else{Node* cur = _root;Node* parent = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->left;}else if (key > cur->_key){parent = cur;cur = cur->right;}}cur = new Node;cur->left = nullptr;cur->right = nullptr;cur->_key = key;cur->_value = value;if (key < parent->_key){parent->left = cur;}else{parent->right = cur;}}return true;}
private:Node* _root = nullptr;
};

三、查找操作find

对于二叉搜索树的查找操作,我们将需要查找的key值与当前结点(初始结点是root结点)比较,若小于该结点的值,则往左子树走;若大于该结点的值,则往右子树走。

若走到空,则说明没有这个值,返回空指针。若找到该值,则返回该值的结点。

	Node* Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->left;}else if (key > cur->_key){cur = cur->right;}else{return cur;}}return nullptr;}

四、删除操作

	bool Erase(const K& key){Node* cur = _root;Node* parent = _root;while (cur){//若key小于当前结点的值,则往左子树走if (key < cur->_key){parent = cur;cur = cur->left;}//若key大于当前结点的值,则往右子树走else if (key > cur->_key){parent = cur;cur = cur->right;}//若key值与当前结点的值相等,则说明该结点就是需要删除的else{//该结点左右子树皆为空的情况if (cur->left == nullptr && cur->right == nullptr){//直接删除if (key < parent->_key){parent->left = nullptr;}if (key > parent->_key){parent->right = nullptr;}delete cur;}//该结点左子树为空的情况else if (cur->left == nullptr){//将该结点的左子树链接到该结点的父结点的子树上,然后删除该结点if (key < parent->_key)parent->left = cur->right;elseparent->right = cur->right;delete cur;}//该结点右子树为空的情况else if (cur->right == nullptr){//将该结点的右子树链接到该结点的父结点的子树上,然后删除该结点if (key < parent->_key)parent->left = cur->left;elseparent->right = cur->left;delete cur;}//左右子树皆不为空//该情况下,我们需要找到左子树的最大结点/右子树的最小结点//然后将需要删除的结点的值和找到的最大结点/最小结点的值交换//此时我们只需要删除交换之后值为需要删除的数值的结点//这里以与左子树的最大结点交换为例else{//del是之后需要删除的结点Node* del = cur->left;//tmp是需要删除的结点的父结点Node* tmp = del;//找到左子树的最大结点,记录为del,此时tmp为del的父结点while (del->right){tmp = del;del = del->right;}//交换key值swap(cur->_key, del->_key);//如即将被删除的结点有左子树,则将其链接到tmp上if (del->left){tmp->right = del->left;}//否则直接将tmp指向即将被删除的结点的指针置空else{tmp->right = nullptr;}//删除交换key值后的结点delete del;}return true;}}return false;}

五、中序遍历InOrder

使用中序遍历二叉搜索树时,我们得到的是一个递增序列。

	void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->left);cout << root->_key << ' ';_InOrder(root->right);}void InOrder(){_InOrder(_root);cout << endl;}

六、完整代码

#include<iostream>
#include<string>template<class K, class V>
struct BSTreeNode
{BSTreeNode<K, V>* left;BSTreeNode<K, V>* right;K _key;V _value;
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public:BSTree(){_root = nullptr;}bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node;_root->_key = key;_root->_value = value;_root->left = nullptr;_root->right = nullptr;}else{Node* cur = _root;Node* parent = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->left;}else if (key > cur->_key){parent = cur;cur = cur->right;}}cur = new Node;cur->left = nullptr;cur->right = nullptr;cur->_key = key;cur->_value = value;if (key < parent->_key){parent->left = cur;}else{parent->right = cur;}}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->left;}else if (key > cur->_key){cur = cur->right;}else{return cur;}}return nullptr;}bool Erase(const K& key){Node* cur = _root;Node* parent = _root;while (cur){//若key小于当前结点的值,则往左子树走if (key < cur->_key){parent = cur;cur = cur->left;}//若key大于当前结点的值,则往右子树走else if (key > cur->_key){parent = cur;cur = cur->right;}//若key值与当前结点的值相等,则说明该结点就是需要删除的else{//该结点左右子树皆为空的情况if (cur->left == nullptr && cur->right == nullptr){//直接删除if (key < parent->_key){parent->left = nullptr;}if (key > parent->_key){parent->right = nullptr;}delete cur;}//该结点左子树为空的情况else if (cur->left == nullptr){//将该结点的左子树链接到该结点的父结点的子树上,然后删除该结点if (key < parent->_key)parent->left = cur->right;elseparent->right = cur->right;delete cur;}//该结点右子树为空的情况else if (cur->right == nullptr){//将该结点的右子树链接到该结点的父结点的子树上,然后删除该结点if (key < parent->_key)parent->left = cur->left;elseparent->right = cur->left;delete cur;}//左右子树皆不为空//该情况下,我们需要找到左子树的最大结点/右子树的最小结点//然后将需要删除的结点的值和找到的最大结点/最小结点的值交换//此时我们只需要删除交换之后值为需要删除的数值的结点//这里以与左子树的最大结点交换为例else{//del是之后需要删除的结点Node* del = cur->left;//tmp是需要删除的结点的父结点Node* tmp = del;//找到左子树的最大结点,记录为del,此时tmp为del的父结点while (del->right){tmp = del;del = del->right;}//交换key值swap(cur->_key, del->_key);//如即将被删除的结点有左子树,则将其链接到tmp上if (del->left){tmp->right = del->left;}//否则直接将tmp指向即将被删除的结点的指针置空else{tmp->right = nullptr;}//删除交换key值后的结点delete del;}return true;}}return false;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->left);cout << root->_key << ' ';_InOrder(root->right);}void InOrder(){_InOrder(_root);cout << endl;}private:Node* _root = nullptr;
};


http://www.ppmy.cn/news/1354940.html

相关文章

九、OpenCV自带colormap

项目功能实现&#xff1a;每隔1500ms轮流自动播放不同风格图像显示&#xff0c;按下Esc键退出 按照之前的博文结构来&#xff0c;这里就不在赘述了 一、头文件 colormap.h #pragma once #include<opencv2/opencv.hpp> using namespace cv;class ColorMap { public:vo…

jsp课程教学管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 JSP 课程教学管理系统是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql5.0…

挑战杯 YOLOv7 目标检测网络解读

文章目录 0 前言1 yolov7的整体结构2 关键点 - backbone关键点 - head3 训练4 使用效果5 最后 0 前言 世界变化太快&#xff0c;YOLOv6还没用熟YOLOv7就来了&#xff0c;如果有同学的毕设项目想用上最新的技术&#xff0c;不妨看看学长的这篇文章&#xff0c;学长带大家简单的…

Linux目录操作类命令 less | grep | ln | chattr | 清除日志内容

less 用来浏览超过一页的文件 用 / 可用来查找关键字 q键退出 cat -n 3.txt | less行号显示grep 文本处理工具&#xff0c;以行为单位找关键字 ls -l /boot | grep ^l grep 关键字 文件名 grep runlevel /etc/inittab 参数 -i忽略大小写 -n显示行号 -v排除关键字&#xff0…

PTA | Wifi密码

下面是微博上流传的一张照片&#xff1a;“各位亲爱的同学们&#xff0c;鉴于大家有时需要使用 wifi&#xff0c;又怕耽误亲们的学习&#xff0c;现将 wifi 密码设置为下列数学题答案&#xff1a;A-1&#xff1b;B-2&#xff1b;C-3&#xff1b;D-4&#xff1b;请同学们自己作答…

前端性能优化的策略和技术手段总结

前端性能优化是提高用户体验和网站运行效率的重要环节。以下是一些常见的策略和技术手段&#xff0c;用于优化前端性能&#xff1a; 1. 优化资源加载 - 合并资源&#xff1a;将多个文件合并为一个文件&#xff0c;减少HTTP请求次数。 - 压缩资源&#xff1a;压缩CSS、J…

[java基础揉碎] 作用域

局部变量与全局变量: 作用域的细节:

用结构体数组,完成宠物信息登记管理。

管理宠物的名字&#xff0c;品种&#xff0c;年龄。 实现功能如下: 1.插入宠物信息 2.遍历宠物信息 #include <stdio.h> #define N 100 typedef struct chongwu { char name[20]; char pingz[10]; int age; }cw; void intset_cw(cw *ptr,int *pnum) { printf("请…

Stable Diffusion webui安装详细教程

上一篇文章介绍了sd主流的ui&#xff0c;相信大家已经有所了解&#xff0c;下面为大家介绍sd-webui的安装详细教程 文章目录 一、 安装包说明二、对电脑的要求三、安装文件介绍四、安装步骤五、电脑问题与云主机六、界面简要说明及通用反向提示词 一、 安装包说明 通常我们使…

【Unity】【VR开发】针对VR项目的优化版Unity Build Settings

【背景】 编辑器中做了功能后,打包后却总会画面不满意,所以到处学习,总结成本篇,希望有用。 【准备】 本篇总结基于Unity 2021 LTS。 模板选择3D(URP) 如果URP不支持所用的部分Assets,那么也可以选择Built-in管线,不过URP肯定画面效果上要胜过Built-in。 HDRP不适用…

并发编程之深入理解JVM并发三大特性

并发编程之深入理解JVM&并发三大特性 并发编程解决的问题 ​ 多线程同步&#xff08;一个线程需要等待另一个线程的结果&#xff0c;一个线程依赖于另一个线程&#xff09;&#xff0c;互斥&#xff08;一个资源只能一个线程使用&#xff09;&#xff0c;分工&#xff08…

普中51单片机学习(六)

点亮第一个LED LED相关知识 LED,即发光二极管&#xff0c;是一种半导体固体发光器件。工作原理为&#xff1a;LED的工作是有方向性的&#xff0c;只有当正级接到LED阳极&#xff0c;负极接到LED的阴极的时候才能工作&#xff0c;如果反接LED是不能正常工作的。其原理图如下 …

【蓝桥杯】算法模板题(Floyd算法)

一.弗洛伊德算法 用途&#xff1a;用来求解多源点最短路径问题。 思想&#xff1a;Floyd算法又称为插点法&#xff0c;是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。 主要步骤&#xff1a; 1&#xff09;初始化&#xff1a;使用邻接矩阵初始化dis…

使用傅里叶实现100倍的压缩效果(附Python源码)

傅里叶变换&#xff08;Fourier Transform&#xff09;是一种将一个函数&#xff08;在时间或空间域&#xff09;转换为另一个函数&#xff08;在频率域&#xff09;的数学变换方法。它在信号处理、图像处理、通信等领域有广泛应用。 实现过程 将傅里叶系数核心的1%保留&…

mysql 2-18

加密与解密函数 其他函数 聚合函数 三者效率 GROUP BY HAVING WHERE和HAVING的区别 子查询 单行子查询和多行子查询 单行比较操作符 多行比较操作符 把平均工资生成的结果当成一个新表 相关子查询 EXISTS 一条数据的存储过程 标识符命名规则 创建数据库 MYSQL的数据类型 创建表…

美国突然致敬中本聪

作者&#xff1a;秦晋 有点看不懂美国的神操作。 2月16日&#xff0c;据《Bitcoin Magazine》报道&#xff0c;比特币的竞争对手、美国参议员伊丽莎白-沃伦对比特币的立场突然180度大转弯。由反对立场转为支持立场。让很多行业媒体出乎意料&#xff0c;甚至惊掉下巴。 报道称&a…

视觉开发板—K210自学笔记(五)--按键控制LED

本期我们来遵循其他单片机的学习路线开始去用板子上的按键控制点亮LED。那么第一步还是先知道K210里面的硬件电路是怎么连接的&#xff0c;需要查看第二节的文档&#xff0c;看看开发板原理图到底是按键是跟哪个IO连在一起。然后再建立输入按键和GPIO的映射就可以开始变成了。 …

模型训练 —— AI算法初识

一、背景 AI算法中模型训练的主要目的是为了让机器学习算法从给定的标注数据中学习规律、特征和模式&#xff0c;并通过调整模型内部参数&#xff0c;使模型能够对未见过的数据进行准确预测或决策。具体来说&#xff1a; 1. **拟合数据**&#xff1a;模型通过训练来识别输入数…

相机图像质量研究(33)常见问题总结:图像处理对成像的影响--锯齿

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…

一个很牛逼的保存页面为html的插件

目录 安装 使用 今天突然发现一个牛逼的插件 直接上链接 https://github.com/gildas-lormeau/SingleFile 安装 SingleFile can be installed on: Firefox: SingleFile – Get this Extension for &#x1f98a; Firefox (en-US)Firefox for Android: SingleFile – Get thi…
最新文章