数据结构——二叉搜索树详解

一、二叉搜索树定义

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

1.非空左子树上所有节点的值都小于根节点的值。

2.非空右子树上所有节点的值都大于根节点的值。

3.左右子树也都为二叉搜索树。

如下图所示：

二、二叉搜索树的操作

二叉搜索树结构：

template<class k>
	struct BSTreeNode {
		typedef BSTreeNode<k> Node;
		Node* _left;//左子树指针
		Node* _right;//右子树指针
		k _key;//节点数据
	};

2.1 二叉搜索树的查找

1.从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

2.最多查找高度次，走到到空，还没找到，这个值不存在。

非递归查找：

bool 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 true;
				}
			}
			return false;
		}

递归查找：

bool _FindR(Node* root, const k& key)
		{
			if (root == nullptr)
				return false;

			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return true;
			}
		}

2.2 二叉搜索树的插入

插入的具体过程如下：

1. 树为空，则直接新增节点，赋值给root指针。

2. 树不空，按二叉搜索树性质查找插入位置，插入新节点。

插入key值为9的节点，如下图所示：

非递归插入：

bool Insert(const k& key) {
			if (_root == nullptr) {
				_root = new Node(key);
				return true;
			}
			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 {
					return false;//key值已存在
				}
			}
			cur = new Node(key);//以key值开辟节点
			if (parent->_key < key) {//新节点>父亲节点，在父亲的右边
				parent->_right = cur;
			}
			if (parent->_key > key) {//新节点<父亲节点，在父亲的左边
				parent->_left = cur;
			}
			return true;
		}

递归插入：

bool _InsertR(Node*& root, const k& key)
		{//递归查找传参指针的引用，修改原指针，让原指针直接指向当前节点
			if (root == nullptr)//root节点为空，开辟新结点
			{
				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;
			}
		}

2.3 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情 况：

1. 要删除的结点无孩子结点 2. 要删除的结点只有左孩子结点 3. 要删除的结点只有右孩子结点 4.要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程 如下：

1.删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除。

2.删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除。 

3.查找删除结点的右子树的最左节点或者左子树的最右节点（距离删除节点最近，替换后不影响其他节点位置），用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除。下面用右子树的最左节点进行替换。

非递归删除：

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
				{
					if (cur->_left == nullptr)//删除节点左边为空
					{
						if (cur == _root)
						{//删除根节点
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)
							{//判断删除节点是parent的left还是right
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_right)
							{//判断删除节点是parent的left还是right
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
						}
						delete cur;
						return true;
					}
					else 
					{
			        //左右子树均有节点，将删除节点替换为其右子树的最左节点（左子树的最右节点）
						Node* rightMinParent = cur;//考虑右子树的根节点为最左节点，不进循环
						Node* rightMin = cur->_right;
						while (rightMin->_left) 
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}
						cur->_key = rightMin->_key;
						if (rightMin == rightMinParent->_left) 
						{
							rightMinParent->_left = rightMin->_right;
                   //rightMin（右子树最左）为替换节点，替换后删除，rightMinParent的左或右指向rightMin的right
						}
						else 
						{
							rightMinParent->_right = rightMin->_right;
						}
						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}

非递归删除：

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
			{
				Node* del = root;//记录要删除的节点
				if (root->_right == nullptr)
				{//删除节点右为空，将左节点赋值给要删除的节点
					root = root->_left;
				}
				else if (root->_left == nullptr)
				{//删除节点左为空，将右节点赋值给要删除的节点
					root = root->_right;
				}
				else
				{
					Node* rightMin = root->_right;
					while (rightMin->_left)
					{
						rightMin = rightMin->_left;
					}
					
					swap(root->_key, rightMin->_key);//交换删除节点和右子树节点的key值
					return _EraseR(root->_right, key);//交换后，删除节点为右子树最左节点，走left为空时情况
				}

				delete del;
				return true;
			}

		}

三、二叉搜索树的模拟实现

//二叉搜索树的模拟实现
namespace rab {
	template<class k>
	struct BSTreeNode {
		typedef BSTreeNode<k> Node;
		Node* _left;
		Node* _right;
		k _key;

		BSTreeNode(const k& key)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};

	template<class k>
	class BSTree {
		typedef BSTreeNode<k> Node;
	public:
		//强制生成构造函数
		BSTree() = default;

		//拷贝构造函数
		BSTree(const BSTree<k>& t)
		{
			_root = Copy(t._root);//传入拷贝对象的根节点
		}

		//析构函数
		~BSTree() {
			Destroy(_root);
		}

		//插入
		bool Insert(const k& key) {
			if (_root == nullptr) {
				_root = new Node(key);
				return true;
			}
			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 {
					return false;//key值已存在
				}
			}
			cur = new Node(key);
			if (parent->_key < key) {
				parent->_right = cur;
			}
			if (parent->_key > key) {
				parent->_left = cur;
			}
			return true;
		}

		//查找
		bool 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 true;
				}
			}
			return false;
		}

		//删除
		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
				{//删除节点左边为空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{//删除根节点
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_right)
							{//判断删除节点是parent的left还是right
								parent->_right = cur->_right;
							}
							else
							{
								parent->_left = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (cur == parent->_right)
							{//判断删除节点是parent的left还是right
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
						}
						delete cur;
						return true;
					}
					else 
					{
						//左右子树均有节点，将删除节点替换为其右子树的最左节点（左子树的最右节点）
						Node* rightMinParent = cur;//考虑右子树的根节点为最左节点，不进循环
						Node* rightMin = cur->_right;
						while (rightMin->_left) 
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}
						cur->_key = rightMin->_key;
						if (rightMin == rightMinParent->_left) 
						{
							rightMinParent->_left = rightMin->_right;//rightMin（右子树最左）为替换节点，替换后删除，rightMinParent的左或右指向rightMin的right
						}
						else 
						{
							rightMinParent->_right = rightMin->_right;
						}
						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}
		
		/二叉搜索树的递归实现
		//递归查找
		bool FindR(const k& key)
		{
			return _FindR(key);
		}

		//递归插入
		bool InsertR(const k& key)
		{
			return _InsertR(_root, key);
		}

		//递归删除节点
		bool EraseR(const k& key)
		{
			return _EraseR(_root, key);
		}

		//中序遍历
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}


	private:
		//递归中序遍历
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;

			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}

		//递归销毁搜索二叉树
		void Destroy(Node* root) {
			if (root == nullptr) {
				return;
			}
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		//前序拷贝构造
		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;
		}
		
		//递归查找
		bool _FindR(Node* root, const k& key)
		{
			if (root == nullptr)
				return false;

			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			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;
			}
		}

		//递归删除
		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
			{
				Node* del = root;
				if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else
				{
					Node* rightMin = root->_right;
					while (rightMin->_left)
					{
						rightMin = rightMin->_left;
					}
					
					swap(root->_key, rightMin->_key);
					return _EraseR(root->_right, key);//交换后，删除节点为右子树最左节点，走left为空时情况
				}

				delete del;
				return true;
			}

		}


	private:
		Node* _root = nullptr;
		};
	}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/494406.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

上位机图像处理和嵌入式模块部署（qmacvisual区域提取）

上位机图像处理和嵌入式模块部署（qmacvisual区域提取）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 在图像处理中&#xff0c;有两部分比较重要&#xff0c;一个是区域分割&#xff0c;一个是区域提取。区域分割&#xff0c;比较好理解&#xff0c;…
阅读更多...
IDEA的使用（概念，安装，配置，）以及什么是字符集，模版

IDEA的使用（概念，安装，配置，）以及什么是字符集，模版

目录 Intellij IDEA IDE的概念 IntelliJ IDEA的安装 IntelliJ IDEA的使用 基本配置 JDK配置 创建Module 基本用法 字体配置 主题配置 字符集 设置IDEA默认字符集 注释模板 字符集 字符集简介 常见字符集 Intellij IDEA 我们不可能一直使用记事本之类变成&#…
阅读更多...
BUG定位---一起学习吧之测试

BUG定位---一起学习吧之测试

判断一个BUG是前端还是后端的&#xff0c;通常需要根据BUG的具体表现、发生的环境以及相关的技术栈来进行分析。以下是一些常用的判断方法&#xff1a; 错误发生的位置&#xff1a; 如果BUG涉及的是页面的布局、样式、交互效果等&#xff0c;那么很可能是前端的BUG。如果BUG与…
阅读更多...
计算机网络：物理层 - 信道复用

计算机网络：物理层 - 信道复用

计算机网络&#xff1a;物理层 - 信道复用 频分复用时分复用统计时分复用波分复用码分复用 计算机网络中&#xff0c;用户之间通过信道进行通信&#xff0c;但是信道是有限的&#xff0c;想要提高网络的效率&#xff0c;就需要提高信道的利用效率。因此计算机网络中普遍采用信道…
阅读更多...
python学习12：python中的字符串格式化-数字精度控制

python学习12：python中的字符串格式化-数字精度控制

python中的字符串格式化-数字精度控制 1.使用辅助符号"m.n"来进行数据的宽度和精度的控制 m,控制宽度&#xff0c;要求是数字&#xff08;一般是很少使用的&#xff09;&#xff0c;设置的宽度小于数字自身&#xff0c;不生效 n,控制小数点精度&#xff0c;要求是数…
阅读更多...
PASSL代码解读[01] readme

PASSL代码解读[01] readme

介绍 PASSL 是一个基于 PaddlePaddle 的视觉库&#xff0c;用于使用 PaddlePaddle 进行最先进的视觉自监督学习研究。PASSL旨在加速自监督学习的研究周期&#xff1a;从设计一个新的自监督任务到评估所学的表征。 PASSL 主要特性&#xff1a; 自监督前沿算法实现 PASSL 实现了…
阅读更多...
自动驾驶传感器：惯性导航IMU原理

自动驾驶传感器：惯性导航IMU原理

自动驾驶传感器&#xff1a;惯性导航IMU原理 附赠自动驾驶学习资料和量产经验&#xff1a;链接 组合导航里包含了GNSS卫星导航模块与IMU惯性导航模块&#xff0c;前一篇文章写了GNSS模块&#xff0c;本章写IMU惯导&#xff0c;也是本系列最后一篇文章。 1. 惯性测量单元&…
阅读更多...
python django实战开发序列化器的一个应用心得分享

python django实战开发序列化器的一个应用心得分享

需求: 查询的时候返回不包括SharePasswd 字段, 但是新增操作需要用到该字段 再不写多个model模型和序列化器的前提下实现 如果您在查询&#xff08;GET 请求&#xff09;时不希望返回 SharePasswd 字段&#xff0c;但在新增&#xff08;POST 请求&#xff09;时需要用到该字段…
阅读更多...
数据结构 - 用队列实现栈/用栈实现队列

数据结构 - 用队列实现栈/用栈实现队列

用栈实现队列 思路&#xff1a; 队列是遵循队头出数据&#xff0c;队列进数据。 创建两个栈&#xff0c;一个左栈&#xff0c;一个右栈。左栈用来插入新数据&#xff0c;右栈用来出数据 我们要借用栈的性质也实现一个出数据&#xff0c;和入数据的功能&#xff0c;该怎么样实…
阅读更多...
[flask]异常抛出和捕获异常

[flask]异常抛出和捕获异常

Python学习之Flask全局异常处理流程_flask 异常处理-CSDN博客 读取文件错误 OSError: [Errno 22] Invalid argument:_[errno 22] invalid argument: ..\\data\\snli_1.0\\-CSDN博客 异常触发 assert触发异常&#xff1a; 在Python中&#xff0c;使用assert语句可以检查某个条…
阅读更多...
“智慧食堂”设计与实现|Springboot+ Mysql+Vue+Java+ B/S结构(可运行源码+数据库+设计文档)

“智慧食堂”设计与实现|Springboot+ Mysql+Vue+Java+ B/S结构(可运行源码+数据库+设计文档)

本项目包含可运行源码数据库LW&#xff0c;文末可获取本项目的所有资料。 推荐阅读100套最新项目持续更新中..... 2024年计算机毕业论文&#xff08;设计&#xff09;学生选题参考合集推荐收藏&#xff08;包含Springboot、jsp、ssmvue等技术项目合集&#xff09; 目录 1. 功…
阅读更多...
Unity urp渲染管线下，动态修改材质球surfaceType

Unity urp渲染管线下，动态修改材质球surfaceType

在项目中遇到了需要代码动态修改材质球的surfaceType&#xff0c;使其动态切换是否透明的需求。 urp渲染管线下&#xff0c;动态修改材质球的surfaceType&#xff0c;查了大部分帖子&#xff0c;都有一些瑕疵&#xff0c;可能会造成透明后阴影投射有问题。 其次在webgl平台上…
阅读更多...
CSS（五）

CSS（五）

一、定位 1.1 为什么需要定位 提问&#xff1a; 以下情况使用标准流或者浮动能实现吗&#xff1f; 1. 某个元素可以自由的在一个盒子内移动位置&#xff0c;并且压住其他盒子. 2. 当我们滚动窗口的时候&#xff0c;盒子是固定屏幕某个位置的。 以上效果&#xff0c;标准流或浮…
阅读更多...
VBA高级应用30例应用2：MouseMove鼠标左键按下并移动鼠标事件

VBA高级应用30例应用2：MouseMove鼠标左键按下并移动鼠标事件

《VBA高级应用30例》&#xff08;版权10178985&#xff09;&#xff0c;是我推出的第十套教程&#xff0c;教程是专门针对高级学员在学习VBA过程中提高路途上的案例展开&#xff0c;这套教程案例与理论结合&#xff0c;紧贴“实战”&#xff0c;并做“战术总结”&#xff0c;以…
阅读更多...
数据安全之路：Databend 用户策略指南

数据安全之路：Databend 用户策略指南

在 Databend 中&#xff0c;我们致力于保护用户的数据安全。除了身份认证之外&#xff0c;我们还提供了多种访问策略&#xff0c;包括网络策略&#xff08;Network Policy&#xff09;、密码策略&#xff08;Password Policy&#xff09;和数据脱敏策略&#xff08;Masking Pol…
阅读更多...
【面试经典150 | 动态规划】三角形最小路径和

【面试经典150 | 动态规划】三角形最小路径和

文章目录 写在前面Tag题目来源解题思路方法一&#xff1a;动态规划 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到的数据结构等内容进行…
阅读更多...
如何使用Docker轻松构建和管理应用程序（二）

如何使用Docker轻松构建和管理应用程序（二）

上一篇文章介绍了 Docker 基本概念&#xff0c;其中镜像、容器和 Dockerfile 。我们使用 Dockerfile 定义镜像&#xff0c;依赖镜像来运行容器&#xff0c;因此 Dockerfile 是镜像和容器的关键&#xff0c;Dockerfile 可以非常容易的定义镜像内容&#xff0c;同时在我们后期的微…
阅读更多...
SpringBoot集成WebSocket实现简单的多人聊天室

SpringBoot集成WebSocket实现简单的多人聊天室

上代码—gitee下载地址&#xff1a; https://gitee.com/bestwater/Spring-websocket.git下载代码&#xff0c;连上数据库执行SQL&#xff0c;就可以运行&#xff0c;最终效果
阅读更多...
二轴机器人大米装箱机：高精度特性如何助力食品工业提升效率与品质?

二轴机器人大米装箱机：高精度特性如何助力食品工业提升效率与品质?

在当今快节奏的工业生产中&#xff0c;食品行业的自动化、智能化水平已成为衡量其竞争力的关键指标。特别是在大米生产线上&#xff0c;如何确保装箱环节的高效与精准&#xff0c;直接关系到企业的生产效率和产品品质。二轴机器人大米装箱机凭借其高精度特性&#xff0c;正逐渐…
阅读更多...
STM32的简介

STM32的简介

内存 一般MCU包含的存储空间有FLASH和RAM,&#xff08;RAM和flash又有片上和片外的区别&#xff0c;片上表示mcu自带的&#xff0c;已经封装在MCU内部的&#xff0c;片外表示外挂的&#xff0c;当项目中需要做一些复杂的应用&#xff0c;会存在资源不足的情况&#xff0c;这时…
阅读更多...
最新文章

Copyright @ 2022~2023