进阶了解C++(5)——搜索二叉树

1. 什么是搜索二叉树：

在之前针对数据结构的文章中，对数、二叉树以及堆进行了介绍，在本部分，将针对二叉搜索树进行介绍。对于二叉搜索树，其于二叉树相比，最大的特点就是结点的排布是存在规则的。在搜索二叉树中，假设根结点存储的数值为 $n$ ，则根结点的右子树所存储的数值均 $>n$ ，根结点的左子树所存储的数值均 $<n$ 。并且其左右子树也都满足这个特点。例如：

2. 搜索二叉树的实现——循环实现：

2.1 搜索二叉树的基本结构：

对于搜索二叉树，其单个结点的结构与二叉树相同，即：一个用于存储数值的变量，两个指针变量，一个指向其左结点，一个指向其右结点。对应代码如下：

template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;

	BSTreeNode(const K& val)
		: _val(val)
		, _left(nullptr)
		, _right(nullptr)
	{}

	K _val;
	Node* _left;
	Node* _right;
};

其中，上面类中的三个成员变量_ $val$ ,_ $left$ ,_ $right$ 分别表示该结点存储的数值，指向的左子树的根结点、指向右子树的根结点。

在利用 $BSTreeNode$ 这个类表示完搜索二叉树中单个结点的结构后，需要对于搜索二叉树的基本结构进行定义，即：将 $BSTreeNode$ 引入，且利用这个类创建一个指针变量表示搜索二叉树的根结点_ $root$ ，并且将其初始化为 $nullptr$ ，即：

template<class K>
class BSTree
{
public:
	typedef BSTreeNode<K> Node;
private:
	Node* _root = nullptr;
};

2.2 搜索二叉树功能实现——搜索结点：

前面说到，搜索二叉树的特点是，根结点的右子树的所有结点存储的数值均 $>$ 根结点存储数值，根结点的左子树所有结点所存储的数值均 $<$ 根结点存储的数值。因此，对于结点的搜索，假设需要搜索的值为 $n$ ，如果满足 $n>root->val$ ,则表示 $n$ 在右子树部分，否则在左子树部分。对应代码如下：

bool Find(const K& val)
{
	Node* cur = _root;
	while (cur)
	{
		if (val > cur->_val)
		{
			cur = cur->_right;
		}
		else if (val < cur->_val)
		{
			cur = cur->_left;
		}
		else
		{
			return true;
		}
	}
	return false;
}

2.3 搜索二叉树功能实现——插入结点：

针对于插入结点这一功能的实现，需要分为两种情况：

1.搜索二叉树为一个空树：

对于空树这种情况，只需要单独对于根结点进行一次检索，即_ $root ==nullptr;$ 如果条件满足，则直接在根结点上利用操作符 $new$ 创建结点即可，机：

bool Insert(const K& val)
{
	if (_root == nullptr)
	{
		_root = new Node(val);
	}
}

2.搜索二叉树不为空：

对于树不为空的情况，首先需要检测插入的数值 $val$ 与根结点存储数值的大小关系，如果大于，则插入在右子树，如果小于，则插入在左子树。需要注意，在搜索二叉树中，不允许存在存储相同数值的结点。具体操作可以由下面的图片演示：

需要插入的数值为 $17$ ，首先创建一个变量 $cur$ 用于接收_ $root$ 的地址，以便进行遍历，在最开始，由于 $17>8$ ,因此 $cur=cur->right$ 。

重复上述步骤，当 $cur$ 指向的结点为存储数值 $14$ 的结点时，由于 $17>14$ ,因此会再次进行 $cur=cur->right$ 的操作，此时 $cur$ 的位置可以如下图所示：

此时，由于没有记录父结点的地址，所以无法进行插入，为了解决这个问题，可以在创建一个变量 $parent$ ，每次 $cur$ 指针的指向改变之前，均让 $parent$ 记录一次 $cur$ 中存储的地址。在加入了 $parent$ 后，当 $cur$ 处于上图中的位置时， $parent$ 的位置可以由下图表示，即：

此时，虽然存储了父结点的地址，但是也不能立即进行插入，需要在对 $cur,parent$ 两个结点中的数值进行一次判定，如果 $cur->val > parent->val;$ 则插入到 $parent$ 的右边，否则插入到左边。对应代码如下：

bool Insert(const K& val)
{
	if (_root == nullptr)
	{
		_root = new Node(val);
	}

	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (val > cur->_val)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (val < cur->_val)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	cur = new Node(val);

	if (val > parent->_val)
	{
		parent->_right = cur;
		return true;
	}
	else if (val < parent->_val)
	{
		parent->_left = cur;
		return true;
	}
}

2.4 搜索二叉树功能实现——中序遍历：

对于中序遍历，在之前针对于二叉树的文章给出过充分的说明，本部分只给出代码，对于不同遍历的具体介绍可以在一起学数据结构（9）——二叉树的链式存储及相关功能实现_链表二叉树存储查询-CSDN博客

进行查看。不过本处需要注意，由于前序遍历需要访问树的根结点，但是根结点的访问权限为 $private$ ，因此，无法在外部直接进行访问。为了解决这个问题，文章选择对前序遍历函数进行一次嵌套，对应代码如下：

void _InOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}

	_InOrder(root->_left);
	cout << root->_val << ' ';
	_InOrder(root->_right);
}

void InOrder()
{
	_InOrder(_root);
}

2.5 搜索二叉树功能测试：

通过下面的代码对于上方的功能函数进行测试：

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

运行结果如下：

2.6 搜索二叉树功能实现——删除结点：

对于搜索二叉树中的删除结点功能，可以说是最复杂的一个功能。因为在删除结点时，需要针对不同的情况来给出特定的删除结点的途径。对于搜索二叉树结点的删除，在大体上可以分为三个部分：

1.删除叶子结点，例如下图中的13，7，4

2.删除的结点有一个子结点，例如下图中的14，10

3.删除的结点有两个子结点，例如下图中的8，6，3

对于上面给出的三种情况，其中第 $1,2$ 种可以看作一种，具体原因在下面给出说明

在删除一个结点之前，首先要找到这个结点，以及这个结点的父结点，对于这类操作在插入中已进行了解释，因此不再过多叙述。假设需要删除存储 $14$ 的结点，则在找到这个结点的地址以及其父结点的地址后，首先需要对存储 $14$ 的结点中的 $left,right$ 进行判断，如果 $left$ 为空，则让父结点链接到 $right$ 。如果 $right$ 为空，则让父结点链接到 $left$ 。如果 $left,right$ 都为空，则可以看作为叶子结点。

例如上图：在找到需要删除的结点 $cur$ 和 $parent$ 后，由于判定 $cur->right==nullptr$ ，因此需要让 $parent$ 链接 $cur->left$ 。但是需要注意，此时并不知道 $parent$ 与 $cur$ 的链接关系，因此，在让 $parent,cur->left$ 链接之前，需要再次进行对于 $parent,cur$ 两个结点关系的判定。如果 $cur=parent->left;$ ，则在链接时，让 $parent->left=cur->left$ 。反之同理。由此，可以得到下面的代码：

bool Erase(const K& val)
{
	Node* cur = _root;
	Node* parent = nullptr;

	while (cur)
	{
		if (val > cur->_val)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (val < cur->_val)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			//找到了需要删除的结点
			if (cur->_left == nullptr)
			{
				if (cur == parent->_left)
				{
					parent->_left = cur->_right;
				}
				else if( cur == parent->_right)
				{
					parent->_right = cur->_right;
				}
				delete cur;
				return true;
			}
			else if (cur->_right == nullptr)
			{
				if (cur == parent->_left)
				{
					parent->_left = cur->_left;
				}
				else if (cur == parent->_right)
				{
					parent->_right = cur->_left;
				}
				delete cur;
				return true;
			}
			else
			{
				;
			}
		}

	}
	return false;
}

在测试代码种，尝试删除存储值为 $14$ 的结点，即：

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

运行结果如下：

如图所示，删除了值为 $14$ 的结点。

目前，上方的代码暂时满足了删除叶子结点或者有一个子结点的结点。但是对于有两个子结点的结点如何删除，例如对于存储数值为 $3$ 的结点，即：

对于拥有两个叶子结点的父结点的删除，文章本处选择替换删除法，即：先找到一个合适的值用于替换待删除结点的值，随后进行删除。

而对于合适的值的选择，需要同时满足两个条件：大于待删除结点的左子树根结点存储的值，小于待删除结点的右子树根结点存储的值。而满足这两个条件的结点，在图中分别为 $2,4$ 。通过搜索二叉树的特点，不难得出，这个合适的点存在于两个地方：

一个是待删除结点的左子树的最右结点，即左子树中的最大的结点。

另一个则是待删除结点的右子树的最左结点，即右子树种的最小的结点。

在进行替换删除法时，对于上面两种结点均可以选择。文章本处选择查找右子树中的最小结点。具体方法如下：

定义一个指针 $rightMin$ ，并且用于存储待删除结点的右子树的根结点，对于上图，则 $rightMin$ 用于存储 $3$ 结点的右子树的根结点，即 $6$ 结点。再令 $rightMin=rightMin->left;$ 来查找右子树的最左结点。并且为了防止让 $rightMin$ 存储空，每次向下查找之前，需要进行一次判定 $rightMin->left\, \, !=\, \, nullptr;$ 。再找到和合适的结点后，将待删除结点的数值改为 $rightMin->val$ 。具体如下：

在进行删除结点时，只需要删除 $rightMin$ 所对应的结点即可。即：

由于需要删除 $rightMin$ 结点，同时还需要让 $rightMin$ 的父结点的指向发生改变，例如上图中的 $6$ 结点。因此，在查找 $rightMin$ 时，还需要找到其父结点，为了方便表达，文章将这个父结点命名为 $rightMinParent$ ，对于上述过程的具体代码如下所示：

Node* rightMin = cur->_right;
Node* rightMinParent = nullptr;
while (rightMin->_left != nullptr)
{
				rightMinParent = rightMin;
				rightMin = rightMin->_left;
}

cur->_val = rightMin->_val;
rightMinParent->_left = rightMin->_right;

但是这种删除方法并不完全正确，例如针对删除根结点 $8$ 这一极端情况，此时 $cur,rightMin,rightMinParent$ 的初始位置可以由下图表示：

如果按照上方的代码运行，由于 $rightMin->left \, \, ==\, \, nullptr$ ，因此 $rightMin$ 的指向不会改变，并且 $rightMinParent$ 的指向也不会改变，即一直为 $nullptr$ 。因此，为了解决这个问题，在初始化 $rightMinParent$ 时，不能初始化为 $nullptr$ ，而是初始化为 $cur$ 。在修改后，此时的三个指针的指向可以由下图进行表示：

但是，如果继续按照上面的代码运行，当运行到

rightMinParent->_left = rightMin->_left;

不难发现，此时 $rightMin\, \, =\, \, rightMinParent->right;$ 因此，会发生错误。所以，在修改 $rightMinParent$ 的指向时，需要在进行一次判定。对应代码如下：

Node* rightMin = cur->_right;
Node* rightMinParent = cur;
while (rightMin->_left != nullptr)
{
				rightMinParent = rightMin;
				rightMin = rightMin->_left;
}

cur->_val = rightMin->_val;
if (rightMin == rightMinParent->_left)
{
				rightMinParent->_left = rightMin->_right;
}
else if (rightMin == rightMinParent->_right)
{
				rightMinParent->_right = rightMin->_right;

}
delete rightMin;
return true;

但是上述代码只能针对完整的树起作用，假设需要对下面图的树的根结点进行删除，即：

按照上面的逻辑，如果待删除的结点左子树为空，则首先需要判断待删除结点是父结点的左子结点还是右子结点。但是，如果删除两面两棵树的根结点 $8$ ，此时并不存在根结点，因此会造成错误。所以，针对删除根结点这一特殊情况需要进行特殊的处理，即：如果根结点的左子树为空，则 $root=root->right$ 反之同理。因此，可以将删除结点的代码完善如下：

bool Erase(const K& val)
{
	Node* cur = _root;
	Node* parent = nullptr;

	while (cur)
	{
		if (val > cur->_val)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (val < cur->_val)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			//找到了需要删除的结点
			if (cur->_left == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					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 = _root->_left;
				}
				else
				{
					if (cur == parent->_right)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
				}
				delete cur;
				return true;
			}
			else
			{
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;
				
				while (rightMin->_left )
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}

				cur->_val = rightMin->_val;
				if (rightMin == rightMinParent->_left)
				{
					rightMinParent->_left = rightMin->_right;
				}
				else
				{
					rightMinParent->_right = rightMin->_right;

				}
				delete rightMin;
				return true;
			}
		}

	}
	return false;
}

3.搜索二叉树的实现——递归实现：

在上面实现中序遍历时说到，由于中序遍历需要树的根结点，但是根结点的访问权限是 $private$ 的，因此，并不能直接使用，需要对中序遍历函数进行一次嵌套。在本处的递归实现搜索二叉树部分，由于递归操作均需要用到根结点，因此，都需要利用函数嵌套来解决这个问题。

3.1 搜索二叉树功能实现——搜索结点：

原理相同，只是将代码改为了递归形式，因此不进行过多解释，只给出代码：

void FindR(const K& val)
{
	_FindR(_root, val);
}

bool _FindR(Node* root, const K& val)
{
	if (root == nullptr)
	{
		return false;
	}

	if (val > root->_val)
	{
		return _FindR(root->_right, val);
	}
	else if (val < root->_val)
	{
		return _FindR(root->_left, val);
	}
	else
	{
		return true;
	}
}

3.2 搜索二叉树功能实现——插入结点：

对于递归实现插入结点这一功能，只需要注意，在给定函数的形式参数用于接收二叉树的根结点时，使用引用可以帮助完成插入结点，具体如下：

void Insert(const K& val)
{
	_Insert(_root, val);
}

bool _Insert(Node*& root, const K& val)
{
	if (root == nullptr)
	{
		root = new Node(val);
		return true;
	}

	if (val > root->_val)
	{
		return _Insert(root->_right, val);
	}
	else if (val < root->_val)
	{
		return _Insert(root->_left, val);
	}
	else
	{
		return false;
	}
}

3.3 搜索二叉树功能实现——删除结点：

原理与循环实现相同，本处只给出代码：

void EraseR(const K& val)
{
	_EraseR(_root, val);
}

bool _EraseR(Node*& root, const K& val)
{
	if (root == nullptr)
	{
		return false;
	}

	if (val > root->_val)
	{
		return _EraseR(root->_right, val);
	}
	else if (val < root->_val)
	{
		return _EraseR(root->_left, val);
	}
	else
	{
		Node* del = root;
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		else
		{
			Node* rightMin = root->_right;
			while (rightMin->_left)
			{
				rightMin = rightMin->_left;
			}

			swap(root->_val, rightMin->_val);

			return _EraseR(root->_right, val);

		}

		delete del;
		return true;
	}
}

3.4 搜索二叉树功能实现——拷贝构造、赋值重载、析构：

本部分只作为额外补充，对于搜索二叉树的意义并不重要，因此只给出代码：

BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}

Node* Copy(Node* root)
{
	if (root == nullptr)
	{
		return nullptr;
	}

	Node* newnode = new Node(root->_val);
	newnode->_left = Copy(root->_left);
	newnode->_right = Copy(root->_right);
	return newnode;

}

~BSTree()
{
	Destory(_root);
}

BSTree<K>& operator=(BSTree<K> t)
{
	swap(_root, t._root);
	return *this;
}

void Destory(Node* root)
{
	if (root == nullptr)
	{
		return;
	}

	Destory(root->_left);
	Destory(root->_right);

	delete root;
}

4. 代码总览：

#include<iostream>
using namespace std;

template<class K>
struct BSTreeNode
{
	typedef BSTreeNode<K> Node;

	BSTreeNode(const K& val)
		: _val(val)
		, _left(nullptr)
		, _right(nullptr)
	{}

	K _val;
	Node* _left;
	Node* _right;
};

template<class K>
class BSTree
{
public:
	typedef BSTreeNode<K> Node;

	BSTree() =default;

	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		Node* newnode = new Node(root->_val);
		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);
		return newnode;

	}

	~BSTree()
	{
		Destory(_root);
	}

	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}
	void Destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		Destory(root->_left);
		Destory(root->_right);

		delete root;
	}
	bool Find(const K& val)
	{
		Node* cur = _root;
		while (cur)
		{
			if (val > cur->_val)
			{
				cur = cur->_right;
			}
			else if (val < cur->_val)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	bool Insert(const K& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (val > cur->_val)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (val < cur->_val)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(val);

		if (val > parent->_val)
		{
			parent->_right = cur;
			return true;
		}
		else if (val < parent->_val)
		{
			parent->_left = cur;
			return true;
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_val << ' ';
		_InOrder(root->_right);
	}

	


	bool Erase(const K& val)
	{
		Node* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			if (val > cur->_val)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (val < cur->_val)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//找到了需要删除的结点
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						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 = _root->_left;
					}
					else
					{
						if (cur == parent->_right)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
					delete cur;
					return true;
				}
				else
				{
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;
					
					while (rightMin->_left )
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}

					cur->_val = rightMin->_val;
					if (rightMin == rightMinParent->_left)
					{
						rightMinParent->_left = rightMin->_right;
					}
					else
					{
						rightMinParent->_right = rightMin->_right;

					}
					delete rightMin;
					return true;
				}
			}

		}
		return false;
	}


	void FindR(const K& val)
	{
		_FindR(_root, val);
	}


	void InsertR(const K& val)
	{
		_InsertR(_root, val);
	}


	void EraseR(const K& val)
	{
		_EraseR(_root, val);
	}

	

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}


private:
	Node* _root = nullptr;

	bool _FindR(Node* root, const K& val)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (val > root->_val)
		{
			return _FindR(root->_right, val);
		}
		else if (val < root->_val)
		{
			return _FindR(root->_left, val);
		}
		else
		{
			return true;
		}
	}

	bool _InsertR(Node*& root, const K& val)
	{
		if (root == nullptr)
		{
			root = new Node(val);
			return true;
		}

		if (val > root->_val)
		{
			return _InsertR(root->_right, val);
		}
		else if (val < root->_val)
		{
			return _InsertR(root->_left, val);
		}
		else
		{
			return false;
		}
	}

	bool _EraseR(Node*& root, const K& val)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (val > root->_val)
		{
			return _EraseR(root->_right, val);
		}
		else if (val < root->_val)
		{
			return _EraseR(root->_left, val);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* rightMin = root->_right;
				while (rightMin->_left)
				{
					rightMin = rightMin->_left;
				}

				swap(root->_val, rightMin->_val);

				return _EraseR(root->_right, val);

			}

			delete del;
			return true;
		}
	}
};

#include"BinarySearchTree.h"


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

	/*for (auto e : a)
	{
		t.EraseR(e);
	}*/
	
	t.InOrder();

	BSTree<int> t1(t);
	t1.InOrder();
	t1 = t;

	return 0;
}