二叉搜索树：从理论到实战，掌握关键操作

用户11831438

发布于 2025-12-30 14:11:26

2830

前言

从二叉搜索树到map和set的使用、AVL树实现、红黑树、封装红黑树实现mymap和myset都是一个整体，也就是说，接下来我们要学习的就是平衡搜索二叉树相关的内容啦。AVL树和红黑树很难，而且不像前面的初阶stl有之前C语言的基础，这是一个非常重要的章节，本章节我们的重点就是介绍map、set的使用和底层，但是在那之前我们要先接触一个数据结构——就是今天我们要介绍的搜索二叉树，有了一定的基础，我们再去接触后面的内容才会更好理解一点。

一、理解二叉搜索树

1.1 二叉搜索树的概念

二叉搜索树又称二叉排序树，二叉搜索树可以是一颗空树，也可以是具有以下性质的二叉树：

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

二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景，后续我们学习的map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等的值，multimap/multiset支持插入相等的值。

如下图所示就是两个搜索二叉树——

1.2 核心特性

1.2.1 多元化的结构：灵活的数据结构

BST支持动态数据集合的高效操作，适合频繁插入、删除和查找的场景。

1.2.2 天然的搜索优势：擅长搜索的数据结构

利用二叉树的分支特性，BST在平均情况下能实现O(logn)的搜索效率。

为什么说二叉搜索树具有高效搜索的特性呢？

1.3 二叉搜索树的性能分析

也许有人会说，二叉搜索树的时间复杂度会是log(N)，其实不是，为什么不是log(N)？

因为二叉搜索数不一定是一棵完全二叉树或者满二叉树，我们只能这么说：

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：

最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：N

所以综合而言，二叉搜索树的时间复杂度为：

那么这样的效率显然是无法满足我们需求的，因此后面会介绍二叉搜索树的变形——平衡二叉搜索树AVL树和红黑树，才能适用于我们在内存中存储和搜索数据。

用中序遍历遍历二叉搜索树出的结果是有序的，并且是从小到大排序！！！

1.3.1 二分查找的局限性

从前面的学习，我们知道二分查找也可以实现

级别的查找效率，但是二分查找有两大缺陷：

需要存储在支持下标随机访问的结构中，并且要求查找前是有序的。
插入和删除数据效率很低，插入和删除数据需要挪动数据

这里也就体现出平衡二叉搜索树的价值：

数据插入的越无序，左右会平衡一点，查找结果会越好（左边的树）
数据越有序，插入结果越坏——高度高、递归深，效率低。（右边的树）

二、手把手实现：二叉搜索树构建指南

2.1 命名规范及定义节点

二叉搜索树常简写为BST，提高代码可读性（SBT不好听），二叉搜索树也叫搜索二叉树。

template<class k>
//struct SearchBinaryTreeNode 
struct BSTreeNode
{
	BSTreeNode<k>* left;//左孩子节点的地址
	BSTreeNode<k>* right;//右孩子节点的地址
	k _key;//关键字，存储数据
	//构造一个节点
	BSTreeNode(const k& key)
		:left(nullptr)
		, right(nullptr)
		, _key(key)
	{}
};

2.2 搜索二叉树的结构

通过前面数据结构中对树的学习，我们知道只要我们知道树的根节点，我们就知道这一整棵树

所以我们可以这样定义搜索二叉树的结构：

template<class k>
class BSTree
{
	typedef BSTreeNode<k> node;
public:
    //一系列操作
private:
	node* _root = nullptr;//根节点
};

2.3 维护树的秩序：插入新元素

插入的具体过程如下：

树为空，则直接新增节点，并让这个节点成为根节点
树不为空，按照搜索二叉树的性质，比较插入值和当前节点中的值的大小，如果大就往右边走；如果小就往左边走，找到空位置，插入新节点
如果支持插入相等的值，插入跟当前节点相等的值可以往当前节点的左边走，也可以往右边走，找到空位置，插入新节点。（注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）

BSTree.h

在这里我们就实现不允许相等的值插入！！！

namespace carrot
{
	template<class k>
	//struct SearchBinaryTreeNode 
	struct BSTreeNode
	{
		BSTreeNode<k>* left;//左孩子节点的地址
		BSTreeNode<k>* right;//右孩子节点的地址
		k _key;//关键字，存储数据
		//构造一个节点
		BSTreeNode(const k& key)
			:left(nullptr)
			, right(nullptr)
			, _key(key)
		{}
	};
	template<class k>
	class BSTree
	{
		typedef BSTreeNode<k> node;
	public:
		//插入数据
		bool insert(const k& key)
		{
			//根节点为空，插入数据成为新的根节点
			if (_root == nullptr)
			{
				_root = new node(key);
				return true;
			}
			//根节点不为空
			//找到要插入的位置然后插入
			node* cur = _root;
			node* parent = nullptr;
			while (cur != nullptr)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					//相等就不插入
					return false;
				}
			}
			//跳出循环，cur的位置就是要插入的位置
			cur = new node(key);
			//cur是插在parent的左边还是右边
			if (parent->_key > key)
			{
				//插在parent的左边
				parent->left = cur;
			}
			else
			{
				//插在parent的右边
				parent->right = cur;
			}
			return true;
		}
	private:
		node* _root = nullptr;//根节点
	};
}

也许会有友友产生一些疑惑，为什么这里要搞个parent 节点，直接让cur成为新节点不就行了吗？

其实这样是不行的，如果直接让cur成为新节点，cur中确实存储了要插入的数据，但是这个cur节点不在这棵树上

也就是这样：

所以我们要找到cur的父节点，让cur和父节点连起来，这样cur就在这棵树上了

ok，现在我们有了一棵搜索二叉树，那我们是不是可以遍历这棵二叉树？那我们怎么遍历这棵二叉树呢？

通过上面的学习，我们知道在中序遍历下，遍历的结果是升序的。那我们就可以使用中序遍历来遍历这颗搜索二叉树——

2.4 中序遍历

有人说，不就是中序遍历吗？简单，直接这么写：

然后调用这个函数的时候，发现root是一个私有成员，在类外面无法访问，只能在类里面访问。其实这是C++中实现递归的一个麻烦之处，在类外面要调用这个函数，但是这个函数要访问私有成员，私有成员只能在类里面访问，类外面无法访问。

此时，我们就可以这样写：

这样我们就可以在类外面调用该函数时，不需要使用私有成员了~~~

BSTree.h

template<class k>
	class BSTree
	{
		typedef BSTreeNode<k> node;
	public:	
    //中序遍历
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
private:
	void _InOrder(node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->left);
		cout << root->_key << " ";
		_InOrder(root->right);
	}
	node* _root = nullptr;//根节点
};

我们插入数据看一下是否成功插入——

namespace carrot
{
	void BSTreetest()
	{
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		BSTree<int> root;
		for (auto& num : a)
		{
			root.insert(num);
		}
		root.InOrder();
	}
}
int main()
{
	carrot::BSTreetest();
	return 0;
}

运行一下：

2.5 高效检索：查找算法的实现

利用BST的排序特性，通过比较键值快速定位目标节点。

查找步骤：

从根节点开始比较，查找x，x比根中的值大则往跟的右边查找，x比根值小则往左边查找
最多查找高度次，走到空，还没有找到，则说明这个值不存在
如果不支持插入相等的值，找到x之后即可返回
如果支持插入相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。如下图，查找3，要找到1的右孩⼦的那个3返回

BSTree.h

//查找数据
bool find(const k& key)
{
	node* cur = _root;
	while (cur != nullptr)
	{
		if (cur->_key > key)
		{
			cur = cur->left;
		}
		else if (cur->_key < key)
		{
			cur = cur->right;
		}
		else
		{
			return true;
		}
	}
	return false;
}

2.6 删除情景分析：处理三种不同情况

搜索二叉树的删除操作是一个比较复杂的操作，这里面涉及了三种情况，让我们来看一下

2.6.1 删除节点没有左右孩子

对于这种删除节点没有左右孩子的节点，我们就可以直接删除该节点哦

2.6.2 删除节点只有左孩子或者右孩子

那对于这种情况我们该怎么做呢？

就比如说你现在想出去玩，但是呢，你的家里有猫猫或者狗狗，猫要铲屎狗要遛，但是呢你又必须要出去玩，该怎么办？

是不是可以把这个猫猫或者狗狗托付给爸爸或者妈妈，让他们帮忙照看一下

ok，这也是同样的道理，删除节点只有左孩子或者右孩子，我可以让我的父节点去照看我的左孩子或者右孩子——

2.6.3 删除节点既有左孩子又有右孩子

我们该怎么办？

ok，我们可以找个节点来替代这个要被删除的节点（要求是：这个节点要比左子树大，要比右子树小），我们可以找左子树中的最大节点或者右子树中的最小节点作为这个节点

那左子树中的最大节点或者右子树中的最小节点是那个节点呢？这两个节点有什么特殊之处？

这样我们就可以找出替换节点——

总结一下删除的步骤： 首先查找元素是否在二叉搜索树中，如果不在，则返回false

如果查找到元素存在，则分为以下四种情况：（假设要删除的节点为N）

要删除节点N左右孩子均为空
要删除节点N左孩子为空，右孩子节点不为空
要删除节点N右孩子为空，左孩子节点不为空
要删除节点N左右孩子节点均不为空

对应以上四种情况的解决方案：

把N节点的父亲对应孩子指针指向空，直接删除N节点（情况1可以当成2或者3处理，效果是一样的）
把N节点的父亲对应孩子指针指向N的右孩子，直接直接删除N节点
把N节点的父亲对应孩子指针指向N的左孩子，直接直接删除N节点
无法直接删除N节点，因为N的两个孩子无法安放，只能用替换法删除。找N 左子树中的最大节点R（最右节点）或者N右子树中的最小节点R（最左节点）替代N。（因为这两个节点中任意一个，放到N的位置，都慢足二叉搜索树的规则）。替换N的意思是N和R的两个节点的值交换，转成删除R节点，若R节点符合情况2或者情况3，可以直接删除；否则还需进行2或者3操作

ok，我们将上面的思路转成代码——

//删除
bool erase(const k& key)
{
	//先查找，找到之后再删除
	node* cur = _root;
	node* parent = nullptr;
	while (cur != nullptr)
	{
		if (cur->_key > key)
		{
			parent = cur;
			cur = cur->left;
		}
		else if (cur->_key < key)
		{
			parent = cur;
			cur = cur->right;
		}
		else
		{
			//找到之后，执行删除操作
			//删除节点的左为空
			if (cur->left == nullptr)
			{
				//让删除节点的父节点指向我的右
				//父节点的左指向我的右还是右指向我的右
				if (parent->left == cur)
				{
					parent->left = cur->right;
				}
				else
				{
					parent->right = cur->right;
				}
				//完成之后，删除cur节点
				delete cur;
				return true;
			}
			//删除节点的右为空
			else if (cur->right == nullptr)
			{
				//让删除节点的父节点指向我的左
				//父节点的左指向我的左还是右指向我的左
				if (parent->left == cur)
				{
					parent->left = cur->left;
				}
				else
				{
					parent->right = cur->left;
				}
				delete cur;
				return true;
			}
			//删除节点左右都不为空
			//需要找替代节点
			else
			{
				//找右子树中的最小节点（最左节点（左孩子为空的节点）），然后替换
				//最左节点（不一定是叶子节点，左孩子为空，右孩子不一定为空）
				node* replaceparent = nullptr;
				node* replace = cur->right;
				while (replace->left)
				{
					replaceparent = replace;
					replace = replace->left;
				}
				//找到之后，替换删除节点
				cur->_key = replace->_key;
				replaceparent->left = replace->right;
				//删除替换节点
				delete replace;
				return true;
			}
		}
	}
	return false;
}

测试结果：

但是，当我们删除根节点时，出现了问题：

我们通过监视窗口看一下，哪里出现了问题：

嗯？replaceparent是空指针？为什么？

所以我们应该让node* replaceparent = cur（cur为根结点）

运行一下：

这是为什么？

我们应该判断一下replaceparent的哪边指向我的右——

我们再重新删除一遍——

namespace carrot
{
	void BSTreetest()
	{
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		BSTree<int> root;
		for (auto& num : a)
		{
			root.insert(num);
		}
		for (auto& e : a)
		{
			root.erase(e);
		}
	}
}
int main()
{
	carrot::BSTreetest();
	return 0;
}

又删除问题了——

这又是什么原因？

ok，当出现下面的情况时，我们需要特殊处理一下：

我们要让根的左孩子或者右孩子成为新的根节点！！！

完整删除代码：

//删除
bool erase(const k& key)
{
	//先查找，找到之后再删除
	node* cur = _root;
	node* parent = nullptr;
	while (cur != nullptr)
	{
		if (cur->_key > key)
		{
			parent = cur;
			cur = cur->left;
		}
		else if (cur->_key < key)
		{
			parent = cur;
			cur = cur->right;
		}
		else
		{
			//找到之后，执行删除操作
			//删除节点的左为空
			if (cur->left == nullptr)
			{
				//如果删除节点为根节点，让根节点的右孩子成为新的根节点
				if (cur == _root)
				{
					_root = cur->right;
				}
				else
				{
					//让删除节点的父节点指向我的右
					//父节点的左指向我的右还是右指向我的右
					if (parent->left == cur)
					{
						parent->left = cur->right;
					}
					else
					{
						parent->right = cur->right;
					}
				}
				//完成之后，删除cur节点
				delete cur;
				return true;
			}
			//删除节点的右为空
			else if (cur->right == nullptr)
			{
				//如果删除节点为根节点，让根节点的左孩子成为新的根节点
				if (cur == _root)
				{
					_root = cur->left;
				}
				else
				{
					//让删除节点的父节点指向我的左
					//父节点的左指向我的左还是右指向我的左
					if (parent->left == cur)
					{
						parent->left = cur->left;
					}
					else
					{
						parent->right = cur->left;
					}
				}
				delete cur;
				return true;
			}

			//删除节点左右都不为空
			//需要找替代节点
			else
			{
				//找删除节点的右子树中的最小节点（最左节点（左孩子为空的节点）），然后替换
				//最左节点（不一定是叶子节点，左孩子为空，右孩子不一定为空）
                //也可以找删除节点的左子树中的最大节点（最右节点（右孩子为空的节点）），然后替换
                //最右节点（不一定是叶子节点，右孩子为空，左孩子不一定为空）
				node* replaceparent = cur;
				node* replace = cur->right;
				while (replace->left)
				{
					replaceparent = replace;
					replace = replace->left;
				}
				//找到之后，替换删除节点
				cur->_key = replace->_key;
				//此时replaceparent->left = replace->right有问题，replaceparent->left有数据
				//所以我们需要判断一下是哪边指向
				if (replaceparent->left == replace)
				{
					replaceparent->left = replace->right;
				}
				else
				{
					replaceparent->right = replace->right;
				}
				//删除替换节点
				delete replace;
				return true;
			}
		}
	}
	return false;
}

测试一下：

完整代码：

BSTree.h

#pragma once
#include<iostream>
using namespace std;
namespace carrot
{
	template<class k>
	//struct SearchBinaryTreeNode 
	struct BSTreeNode
	{
		BSTreeNode<k>* left;//左孩子节点的地址
		BSTreeNode<k>* right;//右孩子节点的地址
		k _key;//关键字，存储数据
		//构造一个节点
		BSTreeNode(const k& key)
			:left(nullptr)
			, right(nullptr)
			, _key(key)
		{}
	};
	template<class k>
	class BSTree
	{
		typedef BSTreeNode<k> node;
	public:
		//插入数据
		bool insert(const k& key)
		{
			//根节点为空，插入数据成为新的根节点
			if (_root == nullptr)
			{
				_root = new node(key);
				return true;
			}
			//根节点不为空
			//找到要插入的位置然后插入
			node* cur = _root;
			node* parent = nullptr;
			while (cur != nullptr)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					//相等就不插入
					return false;
				}
			}
			//跳出循环，cur的位置就是要插入的位置
			cur = new node(key);
			//cur是插在parent的左边还是右边
			if (parent->_key > key)
			{
				//插在parent的左边
				parent->left = cur;
			}
			else
			{
				//插在parent的右边
				parent->right = cur;
			}
			return true;
		}
		//查找数据
		bool find(const k& key)
		{
			node* cur = _root;
			while (cur != nullptr)
			{
				if (cur->_key > key)
				{
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					cur = cur->right;
				}
				else
				{
					return true;
				}
			}
			return false;
		}
		//删除
		bool erase(const k& key)
		{
			//先查找，找到之后再删除
			node* cur = _root;
			node* parent = nullptr;
			while (cur != nullptr)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					//找到之后，执行删除操作
					//删除节点的左为空
					if (cur->left == nullptr)
					{
						//如果删除节点为根节点，让根节点的右孩子成为新的根节点
						if (cur == _root)
						{
							_root = cur->right;
						}
						else
						{
							//让删除节点的父节点指向我的右
							//父节点的左指向我的右还是右指向我的右
							if (parent->left == cur)
							{
								parent->left = cur->right;
							}
							else
							{
								parent->right = cur->right;
							}
						}
						//完成之后，删除cur节点
						delete cur;
						return true;
					}
					//删除节点的右为空
					else if (cur->right == nullptr)
					{
						//如果删除节点为根节点，让根节点的左孩子成为新的根节点
						if (cur == _root)
						{
							_root = cur->left;
						}
						else
						{
							//让删除节点的父节点指向我的左
							//父节点的左指向我的左还是右指向我的左
							if (parent->left == cur)
							{
								parent->left = cur->left;
							}
							else
							{
								parent->right = cur->left;
							}
						}
						delete cur;
						return true;
					}

					//删除节点左右都不为空
					//需要找替代节点
					else
					{
						//找右子树中的最小节点（最左节点（左孩子为空的节点）），然后替换
						//最左节点（不一定是叶子节点，左孩子为空，右孩子不一定为空）
						node* replaceparent = cur;
						node* replace = cur->right;
						while (replace->left)
						{
							replaceparent = replace;
							replace = replace->left;
						}
						//找到之后，替换删除节点
						cur->_key = replace->_key;
						//此时replaceparent->left = replace->right有问题，replaceparent->left有数据
						//所以我们需要判断一下是哪边指向
						if (replaceparent->left == replace)
						{
							replaceparent->left = replace->right;
						}
						else
						{
							replaceparent->right = replace->right;
						}
						//删除替换节点
						delete replace;
						return true;
					}
				}
			}
			return false;
		}
		//中序遍历
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void _InOrder(node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->left);
			cout << root->_key << " ";
			_InOrder(root->right);
		}
		node* _root = nullptr;//根节点
	};
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS
#include"BSTree.h"
namespace carrot
{
	//void BSTreetest()
	//{
	//	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	//	BSTree<int> root;
	//	for (auto& num : a)
	//	{
	//		root.insert(num);
	//	}
	//	root.InOrder();
	//	root.erase(1);
	//	root.InOrder();
	//	root.erase(14);
	//	root.InOrder();
	//	root.erase(3);
	//	root.InOrder();
	//	root.erase(8);
	//	root.InOrder();
	//	/*for (auto& e : a)
	//	{
	//		root.erase(e);
	//	}*/
	//}

	void BSTreetest()
	{
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		BSTree<int> root;
		for (auto& num : a)
		{
			root.insert(num);
		}
		root.InOrder();
		for (auto& e : a)
		{
			root.erase(e);
		}
	}
}
int main()
{
	carrot::BSTreetest();
	return 0;
}

三、二叉搜索树key和key / value使用场景

3.1 key搜索场景

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二又树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。

场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。

场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示

3.2 key / value使用场景

每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中（结点）除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。

场景1：简单中英互译字典，树的结构中（结点）存储key(英文）和vlaue（中文），搜索时输入英文，则同时查找到了英文对应的中文

代码演示：

namespace carrot1
{
	template<class k,class v>
	//struct SearchBinaryTreeNode 
	struct BSTreeNode
	{
		BSTreeNode<k,v>* left;//左孩子节点的地址
		BSTreeNode<k,v>* right;//右孩子节点的地址
		k _key;//关键字，存储数据
		v _values;
		//构造一个节点
		BSTreeNode(const k& key,const v& values)
			:left(nullptr)
			, right(nullptr)
			, _key(key)
			,_values(values)
		{}
	};
	template<class k,class v>
	class BSTree
	{
		typedef BSTreeNode<k,v> node;
	public:
		//插入数据
		bool insert(const k& key,const v& values)
		{
			//根节点为空，插入数据成为新的根节点
			if (_root == nullptr)
			{
				_root = new node(key,values);
				return true;
			}
			//根节点不为空
			//找到要插入的位置然后插入
			node* cur = _root;
			node* parent = nullptr;
			while (cur != nullptr)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					//相等就不插入
					return false;
				}
			}
			//跳出循环，cur的位置就是要插入的位置
			cur = new node(key, values);
			//cur是插在parent的左边还是右边
			if (parent->_key > key)
			{
				//插在parent的左边
				parent->left = cur;
			}
			else
			{
				//插在parent的右边
				parent->right = cur;
			}
			return true;
		}
		//查找数据
		node* find(const k& key)
		{
			node* cur = _root;
			while (cur != nullptr)
			{
				if (cur->_key > key)
				{
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					cur = cur->right;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}
		//删除
		bool erase(const k& key)
		{
			//先查找，找到之后再删除
			node* cur = _root;
			node* parent = nullptr;
			while (cur != nullptr)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else
				{
					//找到之后，执行删除操作
					//删除节点的左为空
					if (cur->left == nullptr)
					{
						//如果删除节点为根节点，让根节点的右孩子成为新的根节点
						if (cur == _root)
						{
							_root = cur->right;
						}
						else
						{
							//让删除节点的父节点指向我的右
							//父节点的左指向我的右还是右指向我的右
							if (parent->left == cur)
							{
								parent->left = cur->right;
							}
							else
							{
								parent->right = cur->right;
							}
						}
						//完成之后，删除cur节点
						delete cur;
						return true;
					}
					//删除节点的右为空
					else if (cur->right == nullptr)
					{
						//如果删除节点为根节点，让根节点的左孩子成为新的根节点
						if (cur == _root)
						{
							_root = cur->left;
						}
						else
						{
							//让删除节点的父节点指向我的左
							//父节点的左指向我的左还是右指向我的左
							if (parent->left == cur)
							{
								parent->left = cur->left;
							}
							else
							{
								parent->right = cur->left;
							}
						}
						delete cur;
						return true;
					}

					//删除节点左右都不为空
					//需要找替代节点
					else
					{
						//找右子树中的最小节点（最左节点（左孩子为空的节点）），然后替换
						//最左节点（不一定是叶子节点，左孩子为空，右孩子不一定为空）
						node* replaceparent = cur;
						node* replace = cur->right;
						while (replace->left)
						{
							replaceparent = replace;
							replace = replace->left;
						}
						//找到之后，替换删除节点
						cur->_key = replace->_key;
						//此时replaceparent->left = replace->right有问题，replaceparent->left有数据
						//所以我们需要判断一下是哪边指向
						if (replaceparent->left == replace)
						{
							replaceparent->left = replace->right;
						}
						else
						{
							replaceparent->right = replace->right;
						}
						//删除替换节点
						delete replace;
						return true;
					}
				}
			}
			return false;
		}
		//中序遍历
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void _InOrder(node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->left);
			cout << root->_key << " ";
			_InOrder(root->right);
		}
		node* _root = nullptr;//根节点
	};
}

场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场——

场景3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，( 单词 , 1），单词存在，则++单词对应的次数。

结尾

写到这里搜索二叉树这一章节就完美散花啦，那请大佬不要忘记给博主来个赞哦！

૮₍ ˶ ˊ ᴥ ˋ˶₎ა

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-30，如有侵权请联系 cloudcommunity@tencent.com 删除

搜索

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度