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

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

article 2025/1/16 21:50:23

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

结果如图：


http://www.kler.cn/a/505547.html

相关文章：

  • Franka例程学习——force_control
  • 算法每日双题精讲 —— 二分查找（二分查找，在排序数组中查找元素的第一个和最后一个位置）
  • Hive集群的安装准备
  • web.xml常用配置
  • Spring Boot 项目启动后自动加载系统配置的多种实现方式
  • 个人主页搭建全流程(Nginx部署+SSL配置+DCDN加速)
  • 使用Struts2遇到的Context[项目名称]启动失败问题解决（Java Web学习笔记）
  • 虚拟线程JDK与Spring Core Reactor
  • 2025windows环境下安装RabbitMQ
  • Frida调试il2cpp的程序打印原生c#对象为json
  • Qt 5.14.2 学习记录 —— 십이 QLineEdit、QTextEdit
  • win32汇编环境,窗口程序中组合框的应用举例
  • 如何将一个数组转换为字符串？
  • 01、kafka知识点综合
  • [Linux]Docker快速上手操作教程
  • LevelDB 源码阅读：如何优雅地合并写入和删除操作
  • 【MySQL学习笔记】MySQL存储过程
  • 通信与网络安全管理之ISO七层模型与TCP/IP模型
  • 计算机后端学习路径（精华版）
  • 仪式感在会员体系建设中的重要性及AI智能名片2+1链动模式S2B2C商城小程序的应用研究
  • 神经网络基础-网络优化方法
  • Lua调用C#
  • YOLOv11 OBB 任务介绍与数据集构建要求及训练脚本使用指南
  • Linux——进程信号
  • rust toml
  • 遥感图像滑坡分类数据集2773张2类别