C++【二叉搜索树】

北海

发布于 2023-07-01 13:53:08

19300

代码可运行

文章被收录于专栏：用户10155340的专栏用户10155340的专栏

运行总次数：0

代码可运行

🌇前言

时隔多日，又回到了二叉树的学习中，在 C++ 进阶中，我们首先要学习二叉搜索树，重新捡起二叉树的相关知识，然后会学习 AVL 树及红黑树，最后会用红黑树封装实现库中的 set 和 map，作为 C++ 进阶中的难度最高峰，整个学习过程非常艰辛，但关关难过关关过，让我们先从比较简单的二叉搜索树开始学习

🏙️正文

1、什么是二叉搜索树？

1.1、定义

二叉搜索树（Binary search tree）是基于二叉树的一种改进版本。因为 普通二叉树没有实际价值，无法进行插入、删除等操作（无意义），但二叉搜索树就不一样了，二叉搜索树对于数据的存储有严格要求：左节点比根小，右节点比根大

因此二叉搜索树的查找效率极高，具有一定的实际价值

下图展示了 普通二叉树与二叉搜索树的区别

所以将数据存入二叉搜索树中进行查找时，理想情况下只需要花费 logN 的时间（二分思想）

这就是 二叉搜索树 名字的由来，搜索（查找）速度很快

1.2、特点

二叉树的基本特点：左比根小，右比根大

若某个节点的 左 节点不为空，则 左 节点的值一定比当前节点的值 小，且其 左 子树的所有节点都比它 小
若某个节点的 右 节点不为空，则 右 节点的值一定比当前节点的值 大，且其 右 子树的所有节点都比它 大
二叉搜索树的每一个节点的 根、左 、右 都满足基本特点

除此之外，二叉搜索树还有一个特点：中序遍历的结果为升序

比如下面这个二叉搜索树，在经过中序遍历（左根右）后的结果为：1 3 4 6 7 8 10 13 14

因此，二叉搜索树也叫 二叉排序树，具有一定的排序价值

下面就来看看 如何从 0 开始实现一棵二叉搜索树

2、二叉搜索树的实现

注：先建出一棵二叉搜索树，再补全剩余功能

2.1、基本框架

跟二叉树一样，二叉搜索树也需要有单独的 节点类 表示单个节点，得益于 C++ 面向对象的特性 我们可以利用类和对象、泛型编程等特点，将二叉搜索树实现的更加全能

#pragma once

#include <iostream>

//部分展开，避免冲突
using std::cout;	//遍历时需要用到
using std::endl;

//命名空间
namespace Yohifo
{
	//利用模板，泛型编程
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode(const K& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{}

		//二叉树包含左节点指针、右节点指针、节点值信息
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;
	};

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	private:
		Node* _root = nullptr;	//二叉搜索树的根
	};
}

二叉搜索树也可以叫做搜索二叉树，但后者的英文简写比较不友好：SBTree，因此推荐叫做二叉搜索树：BSTree

注意： 二叉搜索树的节点类需要写出构造函数，因为后面创建新节点时会用到；二叉搜索树的根可以给个缺省值 nullptr，确保后续判断不会出错

2.2、查找

查找逻辑：

查找值比当前值大时，往右走
查找值比当前值小时，往左走
否则就是相等，即找到了

//===基本功能===
bool Empty() const
{
	return _root == nullptr;
}

bool Find(const K& key) const
{
	//如果为空，则查找失败
	if (Empty())
		return false;

	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.3、插入

插入逻辑与查找差不多，不过 插入把查找的过程当作寻找合适位置进行插入

插入逻辑：

先找到合适的位置（满足基本特点）
如果当前位置不为空（冗余），则插入失败
为空则结束循环，进行插入：创建新节点、判断需要插在左边还是右边、链接新节点完成插入

bool Insert(const K& key)
{
	//如果为空，则就是第一次插入
	if (Empty())
	{
		_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;
}

二叉搜索树的根为多少，取决于谁第一个插入，后序插入的节点都是基于根节点进行插入的

当找到合适位置时，需要根据当前 key 值与父节点的值进行判断，插入至合适的位置（满足基本特点）

插入成功时

插入失败时

当前实现的二叉搜索树不允许冗余，如果想要实现冗余的二叉搜索树，可以规定重复的值插在左边或右边，都是可行的

在确认 新节点的链接位置时，可以通过 parent 与 cur 的 key 值判断，也可以通过原有链接关系判断

如果是通过原有链接判断：parent->_right == cur 需要先创建新节点 new_node（不能覆盖 cur 的值），利用 cur 进行链接判断后，再进行新节点链接
推荐直接使用 key 值判断，省时省力

注意：

在执行循环查找合适位置前，需要创建变量记录父节点的位置，方便后续进行新节点链接
找到合适位置后，需要将新节点与父节点进行比较判断，确认链接在左边还是右边
插入失败返回 false，插入成功返回 true

2.4、删除

二叉搜索树的删除是个麻烦事，需要考虑很多情况，因此 如果面试时考到了二叉搜索树，大概率会考删除操作的实现

删除逻辑：

先依照查找的逻辑，判断目标值是否存在
如果存在，则进行删除：待删除节点有多种可能，需要具体问题具体分析
如果不存在，则删除失败

待删除的节点有以下多种可能：

1、右子树为空 右子树为空时，只 需要将其左子树与父节点进行判断链接即可，无论其左子树是否为空，都可以链接，链接完成后，删除目标节点

2、左子树为空 同理，左子树为空时，将其右子树与父节点进行判断链接，链接完成后删除目标节点

3、左右都不为空 当左右都不为空时，就有点麻烦了，需要找到一个合适的值（即 > 左子树所有节点的值，又 < 右子树所有节点的值），确保符合二叉搜索树的基本特点

符合条件的值有：左子树的最右节点（左子树中最大的）、右子树的最左节点（右子树中最小的），将这两个值中的任意一个覆盖待删除节点的值，都能确保符合要求

这里找的是待删除节点左子树的最右节点

为什么找左子树的最右节点或右子树的最左节点的值覆盖可以符合要求？

因为左子树的最右节点是左子树中最大的值，> 左子树所有节点（除了自己），< 右子树所有节点
右子树的最左节点也是如此，都能符合要求

通俗理解：需要找待删除节点的值的兄弟来镇住这个位置，而它的兄弟自然就是左子树最右节点和右子树最左节点，配合中序遍历结果可以确认

伪删除法：

看不到想要删除的值就可以了，至于多余的节点很好删除，也不需要频繁的改变链接关系

通俗理解：把目标删除值覆盖掉，然后删除自己

bool Erase(const K& key)
{
	if (Empty())
		return false;

	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->_right == nullptr)
			{
				//右为空，考虑将左子树链接
				if (cur == _root)
					_root = cur->_left;
				else
				{
					if (parent->_right == cur)
						parent->_right = cur->_left;
					else
						parent->_left = cur->_left;
				}

				delete cur;
			}
			else if (cur->_left == nullptr)
			{
				//左为空，考虑将右子树链接
				if (cur == _root)
					_root = cur->_right;
				else
				{
					if (parent->_right == cur)
						parent->_right = cur->_right;
					else
						parent->_left = cur->_right;
				}

				delete cur;
			}
			else
			{
				//左右子树都不为空，找左子树的最右节点
				//可以更改为找右子树的最左节点
				parent = cur;
				Node* maxLeft = cur->_left;

				while (maxLeft->_right)
				{
					parent = maxLeft;
					maxLeft = maxLeft->_right;
				}

				//替换，伪删除
				cur->_key = maxLeft->_key;

				if (parent->_right == maxLeft)
					parent->_right = maxLeft->_left;
				else
					parent->_left = maxLeft->_left;

				delete maxLeft;
			}

			return true;
		}
	}

	return false;
}

小结：左右子树都为空时：直接删除 左子树、右子树其中一个为空时：托孤，将另一个子树（孩子）寄托给父节点，然后删除自己 左子树、右子树都不空：找一个能挑起担子的保姆，照顾左右两个子树（孩子），然后删除多余的保姆

注意：

涉及更改链接关系的操作，都需要保存父节点的信息
右子树为空、左子树为空时，包含了删除根节点的情况，此时 parent 为空，不必更改父节点链接关系，更新根节点信息后，删除目标节点即可，因此需要对这种情况特殊处理
右子树、左子树都为空的节点，包含于右子树为空的情况中，自然会处理到
左右子树都不为空的场景中，parent 要初始化为 cur，避免后面的野指针问题

3、二叉搜索树的遍历

二叉搜索树的遍历操作和二叉树一模一样，简单回顾下，至于迭代版的遍历操作，将在相关题解中体现

3.1、前序遍历

前序：根 -> 左 -> 右

在递归遍历时，先打印当前节点值（根），再递归左子树（左），最后递归右子树（右）

因为这里是一个被封装的类，所以面临着一个尴尬的问题：二叉搜索树的根是私有，外部无法直接获取

解决方案：

公有化（不安全，也不推荐）
通过函数获取（安全，但用着很别扭）
将这种需要用到根的函数再封装（完美解决方案）

这里主要来说说方案3：类中的函数可以直接通过 this 指针访问成员变量，但外部可没有 this 指针，于是可以先写一个外壳（不需要传参的函数），在这个外壳函数中调用真正的函数即可，因为这个外壳函数在类中，所以此时可以通过 this 指针访问根 _root

具体操作如下：

	//===遍历===
	void PrevOrder()
	{
		_PrevOrder(_root);
	}

protected:
	void _PrevOrder(const Node* root)
	{
		if (root == nullptr)
			return;

		//前序：根左右
		cout << root->_key << " ";
		_PrevOrder(root->_left);
		_PrevOrder(root->_right);
	}

实际调用时，只能调到 PrevOrder ，因为真正的函数 _PrevOrder 为保护状态，除了自己和继承中的派生类外，其他地方不可访问

通过函数测试上述的功能函数及前序遍历情况

void BSTreeTest6()
{
	Yohifo::BSTree<int> t;

	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	for (auto e : a)
		t.InsertR(e);
	t.PrevOrder();
	cout << endl;

	for (auto e : a)
	{
		t.EraseR(e);
		t.PrevOrder();
		cout << endl << "==============" << endl;
	}
}

注意： 不能通过缺省值的方式解决传递根 _root 的问题，因为缺省值只能是全局变量或常量，而 _root 是变量

3.2、中序遍历

中序：左 -> 根 -> 右

在递归遍历时，先递归左子树（左），再打印当前节点值（根），最后递归右子树（右）

中序遍历也需要用到根，同样对其进行再封装

		void InOrder()
		{
			_InOrder(_root);
		}

protected:
		void _InOrder(const Node* root)
		{
			if (root == nullptr)
				return;

			//中序：左根右
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}

同样的通过函数测试中序遍历结果，看看是否真的是有序

void BSTreeTest7()
{
	Yohifo::BSTree<int> t;

	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	for (auto e : a)
		t.InsertR(e);
	t.InOrder();
	cout << endl;
}

3.3、后序遍历

后序：左 -> 右-> 根

在递归遍历时，先递归左子树（左），再递归右子树（右），最后打印当前节点值（根）

一样需要进行再封装

		void PostOrder()
		{
			_PostOrder(_root);
		}
protected:
		void _PostOrder(const Node* root)
		{
			if (root == nullptr)
				return;

			//后序：左右根
			_PrevOrder(root->_left);
			_PrevOrder(root->_right);
			cout << root->_key << " ";
		}

测试

void BSTreeTest8()
{
	Yohifo::BSTree<int> t;

	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	for (auto e : a)
		t.InsertR(e);
	t.PostOrder();
	cout << endl;
}

4、利用递归重新实现

之前实现的 查找、插入、删除 功能都是通过迭代实现的，其实这些功能都可以使用递归实现，递归实现时，将会用到引用，玩转不同栈帧中的变量

4.1、查找（递归版）

递归查找逻辑：如果当前根的值 < 目标值，递归至右树查找；如果当前根的值 > 目标值，递归至左树查找；否则就是找到了，返回 true

因为此时也用到了根 _root，所以也需要进行再封装

		//===递归实现===
		bool FindR(const K& key) const
		{
			return _FindR(_root, key);
		}
protected:
		//递归实现
		bool _FindR(Node* root, const K& key) const
		{
			//递归至叶子节点也没找到
			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;
		}

实际可用，这里就不再演示执行结果

4.2、插入（递归版）

基于递归查找的逻辑，实现递归插入

此时用到了一个很nb的东西：引用，实际插入时，甚至都不需要改链接关系，直接赋值即可

		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}
protected:
		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;
		}

因为此时的参数是 节点指针的引用，所以在 保持原有链接属性的前提下，改变当前节点，即插入节点

4.3、删除（递归版）

递归删除时也使用了引用，这样可以做到 在不同的栈帧中，删除同一个节点，而非临时变量

同时递归删除还用到了一种思想：转换问题的量级

比如原本删除的是根节点，但根节点之下还有很多节点，直接删除势必会造成大量的链接调整，于是可以找到 “保姆”（左子树的最右节点或右子树的最左节点），将 “保姆” 的值与待删除节点的值交换，此时递归至保姆所在的子树进行删除

因为保姆必然只带一个子树或没有子树，所以删除起来很简单

		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
protected:
		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* maxLeft = root->_left;
					while (maxLeft->_right)
						maxLeft = maxLeft->_right;

					//注意：需要交换
					std::swap(root->_key, maxLeft->_key);

					//注意：当前找的是左子树的最右节点，所以递归从左子树开始
					return _EraseR(root->_left, key);
				}

				delete del;	//释放节点
				return true;
			}
		}

将原本一个难以处理的问题，转换容易处理的问题，这就是递归的巧妙之处

测试递归插入与递归删除

void BSTreeTest4()
{
	Yohifo::BSTree<int> t;

	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	for (auto e : a)
		t.InsertR(e);
	t.InOrder();
	cout << endl;

	for (auto e : a)
	{
		t.EraseR(e);
		t.InOrder();
		cout << endl << "==============" << endl;
	}
}

注意：

再次递归时，需要传递 root->_left 而非 maxLeft，因为此时的 maxLeft 是临时变量，而函数参数为引用
传递 root->_left 的原因：找的保姆出自左子树的最右节点，所以要求左子树中找，不能只传递 root，这样会导致查找失败 -> 删除失败
要使用 swap 交换 maxLeft->_key 与 key，然后递归时，找的就是 key；如果不使用交换而去使用赋值，那么递归查找的仍是 maxLeft->_key，类似于迭代删除时，将多余的节点删除

5、二叉搜索树的细节

接下来处理一些细节相关问题

5.1、销毁

创建节点时，使用了 new 申请堆空间，根据动态内存管理原则，需要使用 delete 释放申请的堆空间，但二叉搜索树是一棵树，不能直接释放，需要 递归式的遍历每一个节点，挨个释放

释放思路：后序遍历思想，先将左右子树递归完后，才释放节点

		~BSTree()
		{
			destory(_root);
		}
protected:
		//细节问题
		void destory(Node*& root)
		{
			if (root == nullptr)
				return;

			//后序销毁
			destory(root->_left);
			destory(root->_right);

			delete root;
			root = nullptr;
		}

注意： 因为销毁需要用到递归，所以再封装一个 destory 函数

5.2、拷贝赋值相关

单棵树销毁没问题，但如果涉及拷贝操作时，销毁会出现问题，这是因为 当前使用的是系统默认生成的拷贝构造、赋值重载函数，是浅拷贝，会导致多个指针指向同一块空间的问题，最终出现重复析构问题，程序运行就崩了

void BSTreeTest9()
{
	Yohifo::BSTree<int> t1;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
		t1.InsertR(e);

	auto t2(t1);	//两个指针指向同一块空间
}

如何解决这个问题？

自己实现拷贝构造函数，顺便把赋值重载函数也实现了，目的是实现深拷贝

深拷贝逻辑：前序遍历的思想，逐个创建好节点，链接后才返回

		//===细节补充===
		BSTree()
			:_root(nullptr)
		{}

		BSTree(BSTree<K>& tree)
			:_root(nullptr)
		{
			_root = _Copy(tree._root);
		}

		BSTree<K> operator=(BSTree<K> tree)
		{
			std::swap(_root, tree._root);
			return *this;
		}
protected:
		Node* _Copy(Node* root)
		{
			//递归拷贝
			if (root == nullptr)
				return nullptr;

			Node* new_root = new Node(root->_key);	//单独 new 一个
			new_root->_left = _Copy(root->_left);
			new_root->_right = _Copy(root->_right);

			return new_root;
		}

实现深拷贝后，就不会发生重复析构问题

注意： 假设写了拷贝构造函数，就需要再写一个默认构造函数，这是规定

6、二叉搜索树的应用场景

凭借着极快的查找速度，二叉搜索树有着一定的实战价值，最典型的有：key 查找模型和 key / value 查找及存储模型

6.1、key 的模型

key 模型的应用场景：在不在

门禁系统
车库系统
检查文章中单词拼写是否正确

这些都是可以利用 key 模型解决，其实我们上面写的就是 key 模型，下面通过一段演示代码，展示 key 模型实现 单词查找系统

void BSTreeWordFind()
{
	vector<string> word = { "apple", "banana", "milk", "harmony" };
	Yohifo::BSTree<string> table;

	for (auto e : word)
		table.Insert(e);

	string str;
	while (cin >> str)
	{
		if (table.Find(str))
			cout << "当前单词 " << str << " 存在于词库中" << endl;
		else
			cout << "当前单词 " << str << " 没有在词库中找到" << endl;
	}
}

key 的模型主要就是用来判断在不在的，本质就是查找，这正是 二叉搜索树的强项

6.2、key / value 的模型

key / value 的模型：应用搜索场景

中英文互译字典
电话号码查询快递信息
电话号码 + 验证码

key / value 模型比 key 模型多一个 value，即 kv 模型除了可以用来查找外，还可以再带一个值用于统计，这其实就是哈希的思想（建立映射关系）

kv 模型需要将代码改一下，新增一个模板参数 class value，插入时新增一个参数，同时操作也会有轻微改动，查找时返回的不再是 bool ，而是指向当前节点的指针，其他操作可以不用变

注：即使是 kv 模型，也只是将 key 作为查找、插入、删除的依据，基本逻辑与 value 没有任何关系，value 仅仅起到一个存储额外值的作用

将代码进行小改动，具体可查看源码

实现一个简单的中英词典

void BSTreeDictionary()
{
	vector<pair<string, string>> word = { make_pair("apple", "苹果"), make_pair("banana", "香蕉"), make_pair("milk", "牛奶"), make_pair("harmony", "鸿蒙")};
	Yohifo::BSTreeKV<string, string> table;

	for (auto e : word)
		table.InsertR(e.first, e.second);

	string str;
	while (cin >> str)
	{
		Yohifo::BSTreeNodeKV<string,string>* ret = table.FindR(str);

		if (ret)
			cout << "当前单词 " << str << " 存在于词库中，翻译为 " << ret->_value << endl;
		else
			cout << "当前单词 " << str << " 没有在词库中找到" << endl;
	}
}

关于 pair

pair 是一个内置类，包括 first、second 和其他操作，主要用于这种 kv 场景，其中 make_pair 是一个仿函数，可以根据两个参数快速创建 pair 对象

实现一个简单的水果数量统计

void BSTreeFruitNum()
{
	vector<string> word = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };
	Yohifo::BSTreeKV<string, int> table;

	for (auto e : word)
	{
		auto ret = table.Find(e);
		if (ret == nullptr)
			table.Insert(e, 1);
		else
			ret->_value++;
	}

	table.InOrder();
}