[数据结构与算法]C++进阶——二叉搜索树

二叉搜索树

这篇文章主要为大家介绍二叉树搜索树的概念、操作、实现以及它的应用。同时学习二叉搜索树也是在为我们后面学习map与set做铺垫，当我们了解了二叉搜索树的特性后，后面将有助于我们更好的理解map和set的特性

二叉搜索树的概念（特征）

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

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

int arr[] = {5,3,4,1,7,8,2,6,0,9};

二叉搜索树的操作

二叉搜索树的查找

根据二叉搜索树的特性，我们在二叉搜索里面查找一个值的时候并不需要去遍历整颗树，而是可以通过给定的key值去比较从而确定我们要找的节点。

查找的思想如下：

1. 如果当前节点的key值小于要查找的key，则去我们当前节点右子树查找。
2. 如果当前节点的key值大于要查找的key，则去我们对当前节点的左子树查找
3. 如果当前节点的key值等于要查找的key，则表示找到了，返回当前节点即可。
4. 如果都已经走到空了，但是还没有找到要查找的key，那么就证明当前二叉树不存在值为key的结点，因此返回nullptr

下面我们通过动图来看一下二叉搜索树查找的过程

查找86：

查找15：

查找的代码实现如下：

一、非递归实现：

        Node* Find(const K& key)
		{
			//如果当前二叉搜索树为空
			//则返回nullptr
			if (_root == nullptr)
			{
				return nullptr;
			}
			Node*  cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					cur = cur->_right;
				}
				//找到了就返回当前节点
				else
				{
					return cur;
				}
			}
			//没找到
			return nullptr;

		}

二、递归实现：

        //递归查找
		Node* _FindR(Node* root, const K& key)
		{
			//如果当前节点为空，返回nullptr
			if (root == nullptr)
			{
				return nullptr;
			}
			//如果当前节点的值比key小
			//则递归到右树去找
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			//如果当前节点的值比key大
			//则递归到左树去找
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			//找到了
			//返回root
			else
			{
				return root;
			}
		}

        Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}

二叉搜索树的性能分析

二叉搜索树的插入和删除操作都必须先查找，查找效率代表了二叉搜索树各个操作的性能。既然我们上面已经学了二叉搜索树的查找，那么接下来我们就来分析一下二叉搜索树的查找效率吧。

大家在上面学习了二叉搜索树的查找之后是不是觉得我们二叉搜索树的查找与二分有点像呢？

的确，二叉搜索树的查找和二分有点像，在有些情况下，每查找一次就去掉一半，时间复杂度就是O（logN）这个时候可能就有人会认为二叉搜索树查找的时间复杂度是O（logN）了，注意我说的是在有些情况下哦，我并不是说在所有情况下，还记得我们之前刚开始学时间复杂度的时候嘛，我们说判断一个算法或者代码的时间复杂度是多少我们一定要去考虑它的最坏情况也也就是那些极端情况才行。

下面我们一起来分析一下

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

通过这张图我们就可以知道：

• 最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN
• 最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2

二叉搜索树的插入

二叉搜索树的插入过程比较简单，具体过程如下：

插入的思想如下：

1. 如果当前二叉搜索树为空，那么我们要插入的结点就作为根节点然后返回true。
2. 如果当前二叉搜索树不为空，利用上面查找的思想找到最后一个大于或者最后一个小于要插入key值的结点，然后用该结点作为要插入结点的父节点，然后将他俩链接起来再返回true。
3. 如果当前二叉搜索树不为空，但是发现二叉搜索树里面已经存在了存有要插入值的结点那么就返回false

我们再来通过动图来看一下插入过程吧！

插入10：

插入的代码实现如下：

一、非递归实现：

        //插入
		bool Insert(const K& key)
		{
			//如果当前二叉搜索树为空
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				//如果当前节点的key值大于要插入的key值
				//则要插入的值应插入到当前节点的左子树中
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				//如果当前节点的key值小于要插入的key值
				//则要插入的值应插入到当前节点的右子树中
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				//如果当前节点的key值与要插入的key值相等
				//则返回false吧，表示插入失败
				else
				{
					return false;
				}
			}
			//走出循环，cur已经走到key值要插入的节点位置上
			//并且当前cur为nullptr

			cur = new Node(key);
			//如果当前父节点的值是大于cur的值的
			//则将父节点的值链接到左孩子上
			if (parent->_key>cur->_key)
			{
				parent->_left = cur;  
			}
			else
			{
				parent->_right = cur;
			}
			return true;

		}

二、递归实现：

我们上面非递归的实现在找到插入位置的同时，还必须得用一个指针来记录它父节点的位置。

这里的递归实现非常巧妙的运用了引用，省掉了记录父节点的指针，大家可以学习一下这种方法。

        //递归插入
		bool _InsertR(Node*& root, const K& key)
		{
			//注意我们这里的root是实参的别名
			//它是我们父节点的左孩子或者右孩子的别名
			//通过这种方法就可以将它与父节点链接起来
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}

			//如果当前节点的值小于要插入的key
			//则递归去我们的右树去插入
			if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			//如果当前节点的值大于要插入的key
			//则递归去我们的左树去插入
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			//如果找到相等值则返回false
			else
			{
				return false;
			}
		}

        Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}

二叉搜索树的删除

二叉搜索树的删除相对于上面的查找与插入就复杂了一些。

二叉搜索树的删除主要分为以下情况：

1. 要删除的元素不在二叉树中或者我们当前二叉搜索树为空树则返回false

2. 要删除的元素在二叉搜索树中

   • a. 要删除的结点无孩子结点（即叶子结点）
   • b. 要删除的结点只有左孩子结点
   • c. 要删除的结点只有右孩子结点
   • d. 要删除的结点既有左孩子结点，又有右孩子结点

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

   • 情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
   • 情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
   • 情况d：对于这种情况我们采用替换法删除结点，即找到该节点左子树中key值最大的结点或者找到该结点右子树中key值最小的结点。将替换结点的值赋给要删除的结点，最后再删除替换结点即可。

下面我们通过动图来看一下二叉搜索树的删除

删除10：

删除62：

删除72：

删除的代码如下：

一、非递归实现：

        //删除
		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			//如果当前二叉搜索树为空，则返回false
			if (cur == nullptr)
			{
				return false;
			}
			//我们既然想删除一个数，那我们就得先找到它
			while (cur)
			{
				//如果当前节点的值大于key
				//则我们去当前节点的左边找
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				//如果当前节点的值小于key
				//我们则去当前节点的右边找
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				//找到这个值了
				//我们就开始删除
				else
				{
					//1.删除叶子节点或者只有一个孩子的节点
					//我们将该结点的孩子托付给父亲节点
					//要删除节点的左孩子为空
					//我们将当前节点的右孩子托付给父亲
					if (cur->_left == nullptr)
					{
						//如果要删除的是根节点
						if (cur == _root)
						{
							_root = cur->_right;
							delete cur;
						}
						else
						{
							//我们还需要判断一下当前节点是父亲节点的左孩子还是右孩子
							if (parent->_left == cur)
							{
								//如果是父节点的左孩子，就将当前节点的右孩子变成父亲的左孩子
								parent->_left = cur->_right;
							}
							//反之则将当前节点的右孩子变成父亲节点的右孩子
							else
							{
								parent->_right = cur->_right;
							}
							//再删除当前节点
							delete cur;
						}
					}
					//如果删除节点的右孩子为空
					//我们则将该节点的左孩子托付给父节点
					//同样的我们也需要判断一下当前节点是父节点的左孩子还是右孩子
					else if (cur->_right == nullptr)
					{
						//如果删除的节点为根节点，这种情况下我们要更新根节点
						//因为当前节点的左孩子不为空，因此我们更新根节点我它的左孩子
						if (cur == _root)
						{
							_root = cur->_left;
							delete cur;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
							//再删除当前节点
							delete cur;
						}
					}
					//删除有两个孩子的节点
					//替换法
					else
					{
						这里的MidParent不能够为nullptr
						否则的话有可能会出现空指针解引用
						比如说删7的时候，MidRight指向8 它的左孩子为空然后不进循环

						//Node* MidParent = cur;
						//Node* MidRight = cur->_right;
						找到替换节点
						//while (MidRight->_left)
						//{
						//	MidParent = MidRight;
						//	MidRight = MidRight->_left;
						//}
						记录要替换的值
						//K min = MidRight->_key;
						这里和上面的逻辑一样
						//if (MidRight->_left == nullptr)
						//{
						//	//我们这里还需要判断一下右侧最小节点是父节点的左孩子还是右孩子
						//	//再将当前节点的非空节点托付给父亲
						//	if (MidParent->_left == MidRight)
						//	{
						//		MidParent->_left = MidRight->_right;
						//	}
						//	else
						//	{
						//		MidParent->_right = MidRight->_right;
						//	}
						//}
						当前节点的右孩子为空
						//else
						//{
						//	//同样我们这里还需要判断一下右侧组最小节点是父节点的左孩子还是右孩子
						//	//再将当前节点的非空节点托付给父亲
						//	if (MidParent->_left == MidRight)
						//	{
						//		MidParent->_left = MidRight->_left;
						//	}
						//	else
						//	{
						//		MidParent->_right = MidRight->_left;
						//	}
						//}
						将孩子托付给父亲之后
						将当前替换节点的值赋给要删除节点的值
						然后删除当前替换节点也就完成了替换
						//cur->_key = min;
						//delete MidRight;


						//递归调用的方式删除
						Node* MidRight = cur->_right;
						//找到替换节点
						while (MidRight->_left)
						{
							MidRight = MidRight->_left;
						}
						//记录要替换的值
						K min = MidRight->_key;
						this->Erase(min);
						cur->_key = min;

					}
					return true;
				}
			}
			return  false;
		}

二、递归实现：

注意：这里的递归实现删除的前两种情况非常巧妙的运用了引用，大家可以学习一下这种方法。

        //注意我们这里还是传的引用
		bool _EraseR(Node*& root, const K& key)
		{
			//要删除首先我们得先找到这个值
			//如果这个值存在，我们就删除它并返回true
			//如果不存在则返回false
			if (root == nullptr)
			{
				return false;
			}

			//如果当前节点的值小于key值
			//则递归到右树去删除
			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			//如果当前节点的值小于key值
			//则递归到右树去删除
			else if (root->_key>key)
			{
				return _EraseR(root->_left, key);
			}
			//找到key值了
			//下面我们来分情况讨论
			else
			{
				//如果当前节点的左孩子为空
				//那么就让父节点链接上它的右孩子
				//然后再释放当前节点
				if (root->_left == nullptr)
				{
					Node* del = root;
					//因为我们上面传的是引用，因此这里的root就是父节点左孩子或者右孩子的别名
					root = root->_right;
					delete del;
				}
				//如果当前节点的右孩子为空
				//那么就让父节点链接上它的右孩子
				//然后再释放当前节点
				else if (root->_right == nullptr)
				{
					Node* del = root;
					root = root->_left;
					delete del;
				}
				//当前节点的左孩子与右孩子都不为空,我们采用替换法
				else
				{
					//法一：
					//Node* MidParent = root;
					//Node* MidRight = root->_right;
					找到替换节点
					//while (MidRight->_left)
					//{
					//	MidParent = MidRight;
					//	MidRight = MidRight->_left;
					//}
					记录要替换的值
					//K min = MidRight->_key;
					这里和上面的逻辑一样
					//if (MidRight->_left == nullptr)
					//{
					//	//我们这里还需要判断一下右侧最小节点是父节点的左孩子还是右孩子
					//	//再将当前节点的非空节点托付给父亲
					//	if (MidParent->_left == MidRight)
					//	{
					//		MidParent->_left = MidRight->_right;
					//	}
					//	else
					//	{
					//		MidParent->_right = MidRight->_right;
					//	}
					//}
					当前节点的右孩子为空
					//else
					//{
					//	//同样我们这里还需要判断一下右侧组最小节点是父节点的左孩子还是右孩子
					//	//再将当前节点的非空节点托付给父亲
					//	if (MidParent->_left == MidRight)
					//	{
					//		MidParent->_left = MidRight->_left;
					//	}
					//	else
					//	{
					//		MidParent->_right = MidRight->_left;
					//	}
					//}
					将孩子托付给父亲之后
					将当前替换节点的值赋给要删除节点的值
					然后删除当前替换节点也就完成了替换
					//root->_key = min;
					//delete MidRight;

					//法二：
					//递归调用的方式删除
					Node* MidRight = root->_right;
					//找到替换节点
					while (MidRight->_left)
					{
						MidRight = MidRight->_left;
					}
					//记录要替换的值
					K min = MidRight->_key;
					// 转换成在root的右子树删除min
					_EraseR(root->_right, min);
					root->_key = min;
				}
				return true;
			}
		}
        bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

二叉搜索树的实现

我们这里实现key二叉搜索树模型

实现代码

namespace mlf
{
	template<class K>
	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;
	private:
		//递归查找
		Node* _FindR(Node* root, const K& key)
		{
			//如果当前节点为空，返回nullptr
			if (root == nullptr)
			{
				return nullptr;
			}
			//如果当前节点的值比key小
			//则递归到右树去找
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			//如果当前节点的值比key大
			//则递归到左树去找
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			//找到了
			//返回root
			else
			{
				return root;
			}
		}
		//递归插入
		bool _InsertR(Node*& root, const K& key)
		{
			//注意我们这里的root是实参的别名
			//它是我们父节点的左孩子或者右孩子的别名
			//通过这种方法就可以将它与父节点链接起来
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}

			//如果当前节点的值小于要插入的key
			//则递归去我们的右树去插入
			if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			//如果当前节点的值大于要插入的key
			//则递归去我们的左树去插入
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			//如果找到相等值则返回false
			else
			{
				return false;
			}
		}

		//注意我们这里还是传的引用
		bool _EraseR(Node*& root, const K& key)
		{
			//要删除首先我们得先找到这个值
			//如果这个值存在，我们就删除它并返回true
			//如果不存在则返回false
			if (root == nullptr)
			{
				return false;
			}

			//如果当前节点的值小于key值
			//则递归到右树去删除
			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			//如果当前节点的值小于key值
			//则递归到右树去删除
			else if (root->_key>key)
			{
				return _EraseR(root->_left, key);
			}
			//找到key值了
			//下面我们来分情况讨论
			else
			{
				//如果当前节点的左孩子为空
				//那么就让父节点链接上它的右孩子
				//然后再释放当前节点
				if (root->_left == nullptr)
				{
					Node* del = root;
					//因为我们上面传的是引用，因此这里的root就是父节点左孩子或者右孩子的别名
					root = root->_right;
					delete del;
				}
				//如果当前节点的右孩子为空
				//那么就让父节点链接上它的右孩子
				//然后再释放当前节点
				else if (root->_right == nullptr)
				{
					Node* del = root;
					root = root->_left;
					delete del;
				}
				//当前节点的左孩子与右孩子都不为空,我们采用替换法
				else
				{
					//法一：
					//Node* MidParent = root;
					//Node* MidRight = root->_right;
					找到替换节点
					//while (MidRight->_left)
					//{
					//	MidParent = MidRight;
					//	MidRight = MidRight->_left;
					//}
					记录要替换的值
					//K min = MidRight->_key;
					这里和上面的逻辑一样
					//if (MidRight->_left == nullptr)
					//{
					//	//我们这里还需要判断一下右侧最小节点是父节点的左孩子还是右孩子
					//	//再将当前节点的非空节点托付给父亲
					//	if (MidParent->_left == MidRight)
					//	{
					//		MidParent->_left = MidRight->_right;
					//	}
					//	else
					//	{
					//		MidParent->_right = MidRight->_right;
					//	}
					//}
					当前节点的右孩子为空
					//else
					//{
					//	//同样我们这里还需要判断一下右侧组最小节点是父节点的左孩子还是右孩子
					//	//再将当前节点的非空节点托付给父亲
					//	if (MidParent->_left == MidRight)
					//	{
					//		MidParent->_left = MidRight->_left;
					//	}
					//	else
					//	{
					//		MidParent->_right = MidRight->_left;
					//	}
					//}
					将孩子托付给父亲之后
					将当前替换节点的值赋给要删除节点的值
					然后删除当前替换节点也就完成了替换
					//root->_key = min;
					//delete MidRight;

					//法二：
					//递归调用的方式删除
					Node* MidRight = root->_right;
					//找到替换节点
					while (MidRight->_left)
					{
						MidRight = MidRight->_left;
					}
					//记录要替换的值
					K min = MidRight->_key;
					// 转换成在root的右子树删除min
					_EraseR(root->_right, min);
					root->_key = min;
				}
				return true;
			}
		}

		void _Destory(Node* root)
		{
			//如果当前节点已经走到空，则返回
			if (root == nullptr)
			{
				return;
			}
			//采用后续遍历的方式去销毁
			_Destory(root->_left);
			_Destory(root->_right);
			delete root;
		}

		Node* _Copy(Node* root)
		{
			//如果当前节点为空，则返回空
			if (root == nullptr)
			{
				return nullptr;
			}

			Node* CopyNode = new Node(root->_key);
			CopyNode->_left = _Copy(root->_left);
			CopyNode->_right = _Copy(root->_right);

			return CopyNode;
		}

	public:
		//构造函数
		BSTree()
			:_root(nullptr)
		{}
		//拷贝构造
		BSTree(const BSTree<K>& t)
		{
			_root = _Copy(t._root);
		}

		//析构函数
		~BSTree()
		{
			_Destory(_root);
			_root = nullptr;
		}

		//赋值运算符重载
		//s1 = s3
		//现代写法
		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}

		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}
		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

		Node* Find(const K& key)
		{
			//如果当前二叉搜索树为空
			//则返回nullptr
			if (_root == nullptr)
			{
				return nullptr;
			}
			Node*  cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					cur = cur->_right;
				}
				//找到了就返回当前节点
				else
				{
					return cur;
				}
			}
			//没找到
			return nullptr;

		}

		//插入
		bool Insert(const K& key)
		{
			//如果当前二叉搜索树为空
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				//如果当前节点的key值大于要插入的key值
				//则要插入的值应插入到当前节点的左子树中
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				//如果当前节点的key值小于要插入的key值
				//则要插入的值应插入到当前节点的右子树中
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				//如果当前节点的key值与要插入的key值相等
				//则返回false吧，表示插入失败
				else
				{
					return false;
				}
			}
			//走出循环，cur已经走到key值要插入的节点位置上
			//并且当前cur为nullptr

			cur = new Node(key);
			//如果当前父节点的值是大于cur的值的
			//则将父节点的值链接到左孩子上
			if (parent->_key>cur->_key)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			return true;

		}
		//删除
		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			//如果当前二叉搜索树为空，则返回false
			if (cur == nullptr)
			{
				return false;
			}
			//我们既然想删除一个数，那我们就得先找到它
			while (cur)
			{
				//如果当前节点的值大于key
				//则我们去当前节点的左边找
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				//如果当前节点的值小于key
				//我们则去当前节点的右边找
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				//找到这个值了
				//我们就开始删除
				else
				{
					//1.删除叶子节点或者只有一个孩子的节点
					//我们将该结点的孩子托付给父亲节点
					//要删除节点的左孩子为空
					//我们将当前节点的右孩子托付给父亲
					if (cur->_left == nullptr)
					{
						//如果要删除的是根节点
						if (cur == _root)
						{
							_root = cur->_right;
							delete cur;
						}
						else
						{
							//我们还需要判断一下当前节点是父亲节点的左孩子还是右孩子
							if (parent->_left == cur)
							{
								//如果是父节点的左孩子，就将当前节点的右孩子变成父亲的左孩子
								parent->_left = cur->_right;
							}
							//反之则将当前节点的右孩子变成父亲节点的右孩子
							else
							{
								parent->_right = cur->_right;
							}
							//再删除当前节点
							delete cur;
						}
					}
					//如果删除节点的右孩子为空
					//我们则将该节点的左孩子托付给父节点
					//同样的我们也需要判断一下当前节点是父节点的左孩子还是右孩子
					else if (cur->_right == nullptr)
					{
						//如果删除的节点为根节点，这种情况下我们要更新根节点
						//因为当前节点的左孩子不为空，因此我们更新根节点我它的左孩子
						if (cur == _root)
						{
							_root = cur->_left;
							delete cur;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
							//再删除当前节点
							delete cur;
						}
					}
					//删除有两个孩子的节点
					//替换法
					else
					{
						这里的MidParent不能够为nullptr
						否则的话有可能会出现空指针解引用
						比如说删7的时候，MidRight指向8 它的左孩子为空然后不进循环

						//Node* MidParent = cur;
						//Node* MidRight = cur->_right;
						找到替换节点
						//while (MidRight->_left)
						//{
						//	MidParent = MidRight;
						//	MidRight = MidRight->_left;
						//}
						记录要替换的值
						//K min = MidRight->_key;
						这里和上面的逻辑一样
						//if (MidRight->_left == nullptr)
						//{
						//	//我们这里还需要判断一下右侧最小节点是父节点的左孩子还是右孩子
						//	//再将当前节点的非空节点托付给父亲
						//	if (MidParent->_left == MidRight)
						//	{
						//		MidParent->_left = MidRight->_right;
						//	}
						//	else
						//	{
						//		MidParent->_right = MidRight->_right;
						//	}
						//}
						当前节点的右孩子为空
						//else
						//{
						//	//同样我们这里还需要判断一下右侧组最小节点是父节点的左孩子还是右孩子
						//	//再将当前节点的非空节点托付给父亲
						//	if (MidParent->_left == MidRight)
						//	{
						//		MidParent->_left = MidRight->_left;
						//	}
						//	else
						//	{
						//		MidParent->_right = MidRight->_left;
						//	}
						//}
						将孩子托付给父亲之后
						将当前替换节点的值赋给要删除节点的值
						然后删除当前替换节点也就完成了替换
						//cur->_key = min;
						//delete MidRight;


						//递归调用的方式删除
						Node* MidRight = cur->_right;
						//找到替换节点
						while (MidRight->_left)
						{
							MidRight = MidRight->_left;
						}
						//记录要替换的值
						K min = MidRight->_key;
						this->Erase(min);
						cur->_key = min;

					}
					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);
		}
	private:
		Node* _root;
	};
}

二叉搜索树的应用

K模型

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

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

• 以单词集合中的每个单词作为key，构建一棵二叉搜索树
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：

• <单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key
• 查询英文单词时，只需给出英文单词，就可快速找到与其对应的key

我们将上面K模型的代码稍微改一下就成了我们KV模型的代码了

模拟实现

namespace KV
{
	template<class K, class V>
	struct BSTreeNode
	{
		//左孩子
		BSTreeNode<K, V>* _left;
		//右孩子
		BSTreeNode<K, V>* _right;
		//当前节点的值
		K _key;
		V _val;
		//构造函数
		BSTreeNode(const K& key, const V& val)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _val(val)
		{}
	};
	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	private:
		//递归查找
		Node* _FindR(Node* root, const K& key)
		{
			//如果当前节点为空，返回nullptr
			if (root == nullptr)
			{
				return nullptr;
			}
			//如果当前节点的值比key小
			//则递归到右树去找
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			//如果当前节点的值比key大
			//则递归到左树去找
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			//找到了
			//返回root
			else
			{
				return root;
			}
		}
		//递归插入
		bool _InsertR(Node*& root, const K& key, const V& val)
		{
			//注意我们这里的root是实参的别名
			//它是我们父节点的左孩子或者右孩子的别名
			//通过这种方法就可以将它与父节点链接起来
			if (root == nullptr)
			{
				root = new Node(key, val);
				return true;
			}

			//如果当前节点的值小于要插入的key
			//则递归去我们的右树去插入
			if (root->_key < key)
			{
				return _InsertR(root->_right, key, val);
			}
			//如果当前节点的值大于要插入的key
			//则递归去我们的左树去插入
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key, val);
			}
			//如果找到相等值则返回false
			else
			{
				return false;
			}
		}

		//注意我们这里还是传的引用
		bool _EraseR(Node*& root, const K& key)
		{
			//要删除首先我们得先找到这个值
			//如果这个值存在，我们就删除它并返回true
			//如果不存在则返回false
			if (root == nullptr)
			{
				return false;
			}

			//如果当前节点的值小于key值
			//则递归到右树去删除
			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			//如果当前节点的值小于key值
			//则递归到右树去删除
			else if (root->_key>key)
			{
				return _EraseR(root->_left, key);
			}
			//找到key值了
			//下面我们来分情况讨论
			else
			{
				//如果当前节点的左孩子为空
				//那么就让父节点链接上它的右孩子
				//然后再释放当前节点
				if (root->_left == nullptr)
				{
					Node* del = root;
					//因为我们上面传的是引用，因此这里的root就是父节点左孩子或者右孩子的别名
					root = root->_right;
					delete del;
				}
				//如果当前节点的右孩子为空
				//那么就让父节点链接上它的右孩子
				//然后再释放当前节点
				else if (root->_right == nullptr)
				{
					Node* del = root;
					root = root->_left;
					delete del;
				}
				//当前节点的左孩子与右孩子都不为空,我们采用替换法
				else
				{
					//法一：
					//Node* MidParent = root;
					//Node* MidRight = root->_right;
					找到替换节点
					//while (MidRight->_left)
					//{
					//	MidParent = MidRight;
					//	MidRight = MidRight->_left;
					//}
					记录要替换的值
					//K min = MidRight->_key;
					这里和上面的逻辑一样
					//if (MidRight->_left == nullptr)
					//{
					//	//我们这里还需要判断一下右侧最小节点是父节点的左孩子还是右孩子
					//	//再将当前节点的非空节点托付给父亲
					//	if (MidParent->_left == MidRight)
					//	{
					//		MidParent->_left = MidRight->_right;
					//	}
					//	else
					//	{
					//		MidParent->_right = MidRight->_right;
					//	}
					//}
					当前节点的右孩子为空
					//else
					//{
					//	//同样我们这里还需要判断一下右侧组最小节点是父节点的左孩子还是右孩子
					//	//再将当前节点的非空节点托付给父亲
					//	if (MidParent->_left == MidRight)
					//	{
					//		MidParent->_left = MidRight->_left;
					//	}
					//	else
					//	{
					//		MidParent->_right = MidRight->_left;
					//	}
					//}
					将孩子托付给父亲之后
					将当前替换节点的值赋给要删除节点的值
					然后删除当前替换节点也就完成了替换
					//root->_key = min;
					//delete MidRight;

					//法二：
					//递归调用的方式删除
					Node* MidRight = root->_right;
					//找到替换节点
					while (MidRight->_left)
					{
						MidRight = MidRight->_left;
					}
					//记录要替换的值
					K min = MidRight->_key;
					V val = MidRight->_val;
					// 转换成在root的右子树删除min
					_EraseR(root->_right, min);
					root->_key = min;
					root->_val = val;
				}
				return true;
			}
		}

		void _Destory(Node* root)
		{
			//如果当前节点已经走到空，则返回
			if (root == nullptr)
			{
				return;
			}
			//采用后续遍历的方式去销毁
			_Destory(root->_left);
			_Destory(root->_right);
			delete root;
		}

		Node* _Copy(Node* root)
		{
			//如果当前节点为空，则返回空
			if (root == nullptr)
			{
				return nullptr;
			}

			Node* CopyNode = new Node(root->_key, root->_val);
			CopyNode->_left = _Copy(root->_left);
			CopyNode->_right = _Copy(root->_right);

			return CopyNode;
		}

	public:
		//构造函数
		BSTree()
			:_root(nullptr)
		{}
		//拷贝构造
		BSTree(const BSTree<K, V>& t)
		{
			_root = _Copy(t._root);
		}

		//析构函数
		~BSTree()
		{
			_Destory(_root);
			_root = nullptr;
		}

		//赋值运算符重载
		//s1 = s3
		//现代写法
		BSTree<K, V>& operator=(BSTree<K, V> t)
		{
			swap(_root, t._root);
			return *this;
		}

		bool InsertR(const K& key, const V& val)
		{
			return _InsertR(_root, key, val);
		}
		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}

		//中序遍历
		void _InOrder(Node* root)
		{
			//走到空了就返回
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_val << endl;
			_InOrder(root->_right);
		}
		//套一层，不然的话需要传一个参数才能遍历有点怪怪的
		void InOrder()
		{
			_InOrder(_root);
		}
	private:
		Node* _root;
	};
}

KV模型的使用

下面我们来使用一下KV模型

实例1：英汉字典

int main()
{
	KV::BSTree<string, string>dict;
	dict.InsertR("string", "字符串");
	dict.InsertR("tree", "树");
	dict.InsertR("left", "左边、剩余");
	dict.InsertR("right", "右边");
	dict.InsertR("sort", "排序");
	dict.InsertR("man", "男人");
	string str;
	while (cin>>str)
	{
		KV::BSTreeNode<string, string>* ret = dict.FindR(str);
		if (ret == nullptr)
		{
			cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
		}
		else
		{
			cout << str << "中文翻译:" << ret->_val << endl;
		}
	}


	return 0;
}

打印结果：

实例2：统计水果出现的次数

void TestBSTree()
{
	string arr[] = { "苹果", "香蕉", "桃子", "火龙果", "苹果", "西瓜", "香蕉", "苹果", "草莓" };
	KV::BSTree<string, int>CountTree;
	for (const auto& str : arr)
	{
		//KV::BSTreeNode<string, int>* ret = CountTree.FindR(str);
		auto ret = CountTree.FindR(str);
		//如果ret为空，表示当前水果在之前没出现过
		//因此它是第一次出现，我们将它插入
		if (ret == nullptr)
		{
			CountTree.InsertR(str, 1);
		}
		//ret不为空，表示当前水果不是第一次出现
		//因此我们只需要让它出现的次数++即可
		else
		{
			ret->_val++;
		}
	}

	CountTree.InOrder();
}

打印结果：

以上就是二叉搜索树的全部内容了，如果觉得文章内容还不错的话希望你能点赞+关注支持一下作者。