数据结构9——二叉搜索树

🥇1.二叉搜索树的概念

二叉搜索树(Binary Search Tree,BST)又称二叉排序树或二叉查找树，其要么是一棵空树，要么具有以下性质：

①：左子树上所有节点的值都小于根节点；

②：右子树上所有节点的值都大于根节点；

③：它的左右子树也都是二叉搜索树。

（于是我们发现：二叉搜索树的中序遍历是一个递增序列。 ）

举例：

（易混淆的点：二叉搜索树是要满足左子树中所有节点的值都要小于根，而不是根的直接子节点小于根即可，即：根的左孩子节点，左子树的孙子节点，重孙节点......都要小于根，右子树也是同样的道理。） 

🥇2. 二叉搜索树的实现

使用泛型编程构造出节点和类：

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:

private:
	Node* _root = nullptr;
};

🥈2.1 二叉搜索树的查找

根据二叉搜索树的定义，二叉搜索树的查找无非就是拿待查找节点与根节点比较，比根大从右边找，比根小从左边找，最多查找树的高度次；

当找到空还未找到，则这个值在此二叉搜索树中不存在。

具体实现如下：

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;
	}

🥈2.2 二叉搜索树的插入

二叉搜索树的插入要注意两种情况：

①树本来就是空树，此时可以直接插入；

②树不为空，先查找到要插入的位置，再插入节点。

具体代码如下：

//插入
	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;
			}
		}
		//找到位置，开始插入
		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

🥈2.3 二叉搜索树的删除

二叉搜索树的删除较为复杂，需要分情况讨论：

情况①：要删除的节点没有孩子

情况②：要删除的节点只有左孩子；

情况③：要删除的节点只有右孩子；

情况④：要删除的节点有两个孩子

实际操作中，可以将①②和①③合并，所以代码实现就只有三种情况：

情况①：要删除的节点没有左孩子（此节点只有右孩子或没有孩子）；

情况②：要删除的节点没有右孩子（此节点只有左孩子或没有孩子）；

①和②可以直接删除目标节点，然后将目标节点的孩子托付给爷爷；

情况③：要删除的节点有两个孩子；

③由于存在两个孩子，所以此时就不能再用“托孤”的方法了，我们可以采用替换法删除：找到一个合适的值换掉要删除的值，然后再删除这个“合适的值”，最后再“托孤”。那么这个所谓“合适的值”该如何寻找呢？到底多合适才算合适呢？

我们知道，二叉搜索树都满足左节点比根小，右节点比根大，换一种说法，根就是这组数据的“中位数”，当删除这个“中位数”时，我们只需再找一个中位数左右两边的值作为新的“中位数”就行了呀！

我们知道二叉搜索树的中序遍历就是一个递增序列，所以：

根左边的值是根的左子树的最右节点（以下图为例，8的左子树的最右节点就是7）；

根右边的值是根的右子树的最左节点（以下图为例，8的右子树的最左节点就是10）。

（我们以寻找根的右子树的最左节点作为替换值进行代码实现）

具体代码如下：

//删除
	bool Erase(const K& key)
	{
		//1.先查找要删除的节点
		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;
			}
			//2.查找到要删除的节点
			else
			{
				//①要删除的节点没有左孩子（此节点只有右孩子或没有孩子）
				if (cur->_left == nullptr)
				{
					if (cur == _root)//根节点单独处理
					{
						_root = cur->_right;
					}
					else//只有右孩子，将右孩子托付给爷爷（如上图的节点10）“托孤”
					{
						if (cur == parent->_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//只有左孩子，将左孩子托付给爷爷（如上图的节点14）“托孤”
					{
						if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}

					delete cur;
					return true;
				}
				//③要删除的节点有两个孩子（如上图的节点3、6、8）
				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;
					else
						rightMinParent->_right = rightMin->_right;

					delete rightMin;
					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);
	}

🥈测试

int main()
{
	BSTree<int> t;
	int a[] = { 3,6,9,1,4,2,7,5,8,10 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();
	t.Erase(9);
	t.InOrder();
	t.Insert(52);
	t.InOrder();
	return 0;
}

结果如图：

 

🥇3.二叉搜索树的应用

学了二叉搜索树，可是二叉搜索树到底有什么实际的用途呢？接下来就介绍二叉搜索树的两个模型：K模型和KV模型。

🥈3.1 K 模型

K模型：只有Key作为关键码，结构中只需要存储Key，关键码即为需要搜索到的值。

比如：学校的门禁通过扫脸分辨此人是否为校内人员，具体方式如下：

以每个学生的脸部特征作为Key，构建一棵二叉搜索树；

在二叉搜索树中检索该学生是否存在，存在则开门禁，不存在则不开门禁。

具体实现如下：（为方便演示，这里以学生姓名设置Key，K模型的代码与2中二叉搜索树的实现相似，不同的是需要修改Find函数的返回值和返回类型）

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//查找
	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;
	}

private:
	Node* _root = nullptr;
};

int main()
{
	BSTree<string> Stu;
	Stu.Insert("张三");
	Stu.Insert("李四");
	Stu.Insert("王五");
	Stu.Insert("赵六");
	Stu.Insert("田七");
	string str;
	while (cin >> str)
	{
		auto ret = Stu.Find(str);
		if (ret)
		{
			cout << "开门" << endl;
		}
		else
		{
			cout << "保持关闭" << endl;
		}
	}
	return 0;
}

结果如图：

🥈3.2 KV模型

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。

KV模型相较于K模型更常见，比如：查找英汉词典中英文与中文的对应关系<English,Chinese>；查找学生姓名与性别的对应关系<Name,Sex>。

还以后者为例进行代码实现：

//KV模型
namespace Key_Value
{
	template<class K,class V>
	struct BSTreeNode
	{
		typedef BSTreeNode<K, V> Node;

		Node* _left;
		Node* _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:
		//查找
		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 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)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}
			//找到位置，开始插入
			cur = new Node(key, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}

		//删除
		bool Erase(const K& key)
		{
			//1.先查找要删除的节点
			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;
				}
				//2.查找到要删除的节点
				else
				{
					//①要删除的节点没有左孩子（此节点只有右孩子或没有孩子）
					if (cur->_left == nullptr)
					{
						if (cur == _root)//根节点单独处理
						{
							_root = cur->_right;
						}
						else//只有右孩子，将右孩子托付给爷爷（如上图的节点10）“托孤”
						{
							if (cur == parent->_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//只有左孩子，将左孩子托付给爷爷（如上图的节点14）“托孤”
						{
							if (cur == parent->_right)//判断父亲是爷爷的左孩子还是右孩子，以便于继承父亲的位置
							{
								parent->_right = cur->_left;
							}
							else
							{
								parent->_left = cur->_left;
							}
						}

						delete cur;
						return true;
					}
					//③要删除的节点有两个孩子（如上图的节点3、6、8）
					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;
						else
							rightMinParent->_right = rightMin->_right;

						delete rightMin;
						return true;
					}
				}
			}

			return false;
		}

		//遍历
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;

			_InOrder(root->_left);
			std::cout << root->_key << " ";
			_InOrder(root->_right);
		}
		void InOrder()
		{
			_InOrder(_root);
			std::cout << std::endl;
		}
	private:
		Node* _root = nullptr;
	};
}

int main()
{
	Key_Value::BSTree<string, string> Stu;
	Stu.Insert("张三", "男");
	Stu.Insert("李四", "女");
	Stu.Insert("王五", "男");
	Stu.Insert("赵六", "女");
	Stu.Insert("田七", "女");
	string str;
	while (cin >> str)
	{
		auto ret = Stu.Find(str);
		if (ret)
		{
			cout << ret->_value << endl;
		}
		else
		{
			cout << "查无此人" << endl;
		}
	}
	return 0;
}

结果如图：

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

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

相关文章

如何使用wireshark 解密TLS-SSL报文

如何使用wireshark 解密TLS-SSL报文

目录 前言 原理 操作 前言 现在网站都是https 或者 很多站点都支持 http2。这些站点为了保证数据的安全都通过TLS/SSL 加密过&#xff0c;用wireshark 并不能很好的去解析报文&#xff0c;我们就需要用wireshark去解密这些报文。我主要讲解下mac 在 chrome 怎么配置的&…
阅读更多...
c++ haru生成pdf输出文本实例

c++ haru生成pdf输出文本实例

haru是一个开源的生成pdf的库&#xff0c;花时间终于编译成功&#xff0c;以下是一个特别简单的写文本的实例&#xff1a; #include "hpdf.h" void CDemoDlg::OnBnClickedOk() { HPDF_Error_Handler error_handler NULL; HPDF_Doc pdf; pdf HPDF_New(…
阅读更多...
Redis与MySQL主从复制原理解析

Redis与MySQL主从复制原理解析

目录 1. 介绍2. Mysql主从复制的工作原理3. Mysql复制的类型3.1 基于语句的复制&#xff08;Statement-based Replication, SBR&#xff09;3.2 基于行的复制&#xff08;Row-based Replication, RBR&#xff09;3.3 混合复制&#xff08;Mixed Replication&#xff09; 4. Red…
阅读更多...
一步到位Python Django部署，浅谈Python Django框架

一步到位Python Django部署，浅谈Python Django框架

Django是一个使用Python开发的Web应用程序框架&#xff0c;它遵循MVC&#xff08;Model-View-Controller&#xff09;设计模式&#xff0c;旨在帮助开发人员更快、更轻松地构建和维护高质量的Web应用程序。Django提供了强大的基础设施和工具&#xff0c;以便于处理复杂的业务逻…
阅读更多...
迅为RK3568开发板篇OpenHarmony配置HDF驱动控制LED-新增 topeet子系统-编写 bundle.json文件

迅为RK3568开发板篇OpenHarmony配置HDF驱动控制LED-新增 topeet子系统-编写 bundle.json文件

bundle.json 文件内容如下所示&#xff1a; 下面是对各个字段的解释&#xff1a; 1. name: "ohos/demos" - 这是组件或项目的名称&#xff0c;这里表示它属于 OHOS&#xff08;OpenHarmony OS&#xff09;生态系统下的一个名为"demos"的组件。 2. descri…
阅读更多...
STM32 物联网智能家居 (三) 输入子系统

STM32 物联网智能家居 (三) 输入子系统

STM32 物联网智能家居 (三) 输入子系统 下面是物联网智能家居的输入子系统&#xff0c;见下图&#xff0c;在输入子系统中会实现按键输入、网络输入、标准输入Scanf&#xff0c;其中的网络输入放入到网络子系统中进行讲解。 一、输入子系统核心功能 STM32 物联网智能家居输入…
阅读更多...
Windows 正确配置android adb调试的方法

Windows 正确配置android adb调试的方法

下载适用于 Windows 的 SDK Platform-Tools https://developer.android.google.cn/tools/releases/platform-tools?hlzh-cn 设置系统变量&#xff0c;路径为platform-tools文件夹的绝对路径 点击Path添加环境变量 %adb%打开终端输入adb shell 这就成功了&#xff01;
阅读更多...
【C#深度学习之路】如何使用C#实现Yolo8/11 Segment 全尺寸模型的训练和推理

【C#深度学习之路】如何使用C#实现Yolo8/11 Segment 全尺寸模型的训练和推理

【C#深度学习之路】如何使用C#实现Yolo8/11 Segment 全尺寸模型的训练和推理 项目背景项目实现推理过程训练过程 项目展望写在最后项目下载链接 本文为原创文章&#xff0c;若需要转载&#xff0c;请注明出处。 原文地址&#xff1a;https://blog.csdn.net/qq_30270773/article…
阅读更多...
线性回归超详解

线性回归超详解

目录 一、回归问题 vs 分类问题 二、线性回归 1、一句话理解 2、数学推导 2.1 线性函数表示 2.2 损失函数 2.3 梯度下降 2.3.1 什么是梯度 2.3.2 梯度下降目标 2.3.3 过程 2.3.4 迭代公式 3、特征预处理 3.1 为什么要预处理 3.2 数据归一化方法 1&#xff09;最小…
阅读更多...
docker 部署 Kafka 单机和集群

docker 部署 Kafka 单机和集群

一、准备工作 安装 Docker 确保本机已安装 Docker。可以通过以下命令检查 Docker 是否已安装&#xff1a;docker --version如果未安装&#xff0c;可以访问 Docker 官网下载并安装 Docker Desktop&#xff08;Windows 和 Mac&#xff09;或使用包管理器安装&#xff08;Linux&…
阅读更多...
Uniapp开发安卓App，配置第一次打开软件出现的弹窗-隐私政策提示框

Uniapp开发安卓App，配置第一次打开软件出现的弹窗-隐私政策提示框

这里是直接使用的uniapp官方所提供的“原生隐私政策提示框”&#xff0c;废话不多说&#xff0c;直接上教程&#xff01; 1.manifest.json—>安卓/IOS启动界面配置—>勾选“使用原生隐私政策提示框”2.勾选后&#xff0c;在你的项目下就会出现一个文件&#xff0c;andro…
阅读更多...
微信小程序：播放音频

微信小程序：播放音频

在小程序开发中&#xff0c;音频播放是一个重要的功能。本文将详细介绍小程序音频播放的相关知识点&#xff0c;帮助开发者更好地掌握小程序音频播放的实现方法。 一、小程序音频播放的基本流程 在小程序中&#xff0c;音频播放的基本流程如下&#xff1a; 获取音频数据&#…
阅读更多...
Unity解决滑动条的value值的滑动条消失问题

Unity解决滑动条的value值的滑动条消失问题

在这里我们看到原本的value的滑动条消失了 解决办法 把编辑器的边框往外面拉一下就可以了&#xff08;之前遇到这个问题还重启了几次unity没想到居然是这个问题&#xff09;
阅读更多...
Mac上安装Label Studio

Mac上安装Label Studio

在Mac上安装Anaconda并随后安装Label Studio&#xff0c;可以按照以下步骤进行&#xff1a; 1. 在Mac上安装Anaconda 首先&#xff0c;你需要从Anaconda的官方网站下载适用于Mac的安装程序。访问Anaconda官网&#xff0c;点击“Download Anaconda”按钮&#xff0c;选择适合M…
阅读更多...
微软震撼发布：Phi-4语言模型登陆Hugging Face

微软震撼发布：Phi-4语言模型登陆Hugging Face

近日&#xff0c;微软公司在Hugging Face平台上正式发布了其最新的语言模型Phi-4&#xff0c;这一发布标志着人工智能技术的又一重要进步。Phi-4模型以其140亿参数的高效配置&#xff0c;在复杂推理任务中表现出色&#xff0c;特别是在数学领域&#xff0c;更是展现出了卓越的能…
阅读更多...
使用WebdriverIO和Appium测试App

使用WebdriverIO和Appium测试App

1.新建项目 打开Webstorm新建项目 打开终端输入命令 npm init -y npm install wdio/cli allure-commandline --save-dev npx wdio config 然后在终端依次选择如下&#xff1a; 然后在终端输入命令&#xff1a; npm install wdio/local-runnerlatest wdio/mocha-frameworkla…
阅读更多...
【opencv】第7章 图像变换

【opencv】第7章 图像变换

7.1 基 于OpenCV 的 边 缘 检 测 本节中&#xff0c;我们将一起学习OpenCV 中边缘检测的各种算子和滤波器——Canny 算子、Sobel 算 子 、Laplacian 算子以及Scharr 滤波器。 7.1.1 边缘检测的一般步骤 在具体介绍之前&#xff0c;先来一起看看边缘检测的一般步骤。 1.【第…
阅读更多...
浙江安吉成新照明电器：Acrel-1000DP 分布式光伏监控系统应用探索

浙江安吉成新照明电器：Acrel-1000DP 分布式光伏监控系统应用探索

安科瑞吕梦怡 18706162527 摘 要&#xff1a;分布式光伏发电站是指将光伏发电组件安装在用户的建筑物屋顶、空地或其他适合的场地上&#xff0c;利用太阳能进行发电的一种可再生能源利用方式&#xff0c;与传统的大型集中式光伏电站相比&#xff0c;分布式光伏发电具有更灵活…
阅读更多...
Linux检查磁盘占用情况

Linux检查磁盘占用情况

1.检查使用情况 df -h发现是/dev/vda1占用很高 2.查看/dev/vda1文件夹 cd /dev/vda1发现不是文件夹 3.继续查看使用情况 df -h *4.原因可能是文件已经删除但是进程还在&#xff0c;没有释放空间 5.查看删除操作的进程 lsof -n | grep deleted6.杀死进程 kill -9 PID
阅读更多...
向量数据库Milvus详解

向量数据库Milvus详解

向量数据库Milvus详解 0. 什么是向量数据库？ 在现实世界中，并非所有数据都可以整齐地放到行和列中。在处理图像、视频和自然语言等复杂的非结构化数据时尤其如此。这就是向量数据库的用武之地。 向量数据库是一种以高维向量的形式来存储数据的数据库，这些向量本质上是表示…
阅读更多...
最新文章

Copyright @ 2022~2023