C++数据结构二叉搜索树的实现应用与分析

?概念

二叉搜索树又称为二叉排序书，因为这棵树的中序遍历是有序的。二叉搜索树总结起来有以下几个性质：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于于根节点的值
它的左右子树都是二叉搜索树
这棵树中没有重复的元素

?二叉搜索树的实现

?基本框架

由一个节点的成员构成，先构建节点的类型，和我们之前数据结构中的二叉树的节点定义是一样的。二叉搜索树的根节点先默认给空。

template <class K, class V>
struct BSTNode
{
	BSTNode<K, V>* _left;
	BSTNode<K, V>* _right;
	K _key;
	V _value;

	BSTNode(const K& key, const V& value)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
		,_value(value)
	{}
};
template <class K, class V>
class BSTree //Binary Search Tree
{
	typedef BSTNode<K, V> Node;
private:
	Node* _root = nullptr;
};

?二叉搜索树的插入

插入分为下面几个步骤：

先判断树是否为空，为空就让要插入的这个节点作为根节点，然后结束
部署就确定要插入节点的位置
用一个cur记录当前节点，parent记录父节点
要插入节点的值如果比当前节点的值小，cur就往左走，如果比当前节点的值大，就往右子树走，如果等于就返回false，表面这棵树中有这个数据，不需要插入。

下面是一个简单的动图演示

请添加图片描述

注意：这里不用担心新插入节点会在树中间插入，它一定是在最下面插入的，它会走到最下面，然后在树的底部插入。

代码实现如下：

bool Insert(const K& key, const V& value)
{
	// 没有节点时第一个节点就是根节点
	if (_root == nullptr)
	{
		_root = new Node(key, value);
		return true;
	}

	// 用一个父亲节点记录cur的上一个节点
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		parent = cur;
		// 小于往左边走
		if (key < cur->_key)
			cur = cur->_left;
		else if (key > cur->_key)
			cur = cur->_right;
		else
			return false;// 已有的节点不插入，此次插入失败
	}

	cur = new Node(key, value);
	// 判断应该插在父节点的左边还是右边
	if (cur->_key < parent->_key)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}

	return true;
}

为了更好地观察这棵树插入后是否有效，我们可以实现一个中序遍历，将其打印出来。中序遍历代码如下：

void InOrder()
{
	// 利用子函数遍历
	_InOrder(_root);
	cout << endl;
}
void _InOrder(Node* root)
{
	if (root == nullptr)
		return;

	_InOrder(root->_left);
	cout << root->_key << ":" << root->_value << endl;
	_InOrder(root->_right);
}

测试代码如下：

void TestBSTree()
{
	BSTree<int> bt;
	int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
	//int arr[] = { 1,2,3,4 };
	//int arr[] = { 4,3,2,1};
	for (auto e : arr)
	{
		bt.Insert(e);
	}

	bt.InOrder();
}

代码运行结果如下：

?二叉搜索树的查找

查找的步骤如下：（和插入的步骤有些类似）

如果查找值key比当前节点的值小，就往左子树走
如果查找值key比当前节点的值大，就往右子树走
如果查找值key和当前节点的值相等，就返回当前节点的指针

代码实现如下：

Node* Find(const K& key)
{
	if (_root == nullptr)
		return nullptr;
	Node* cur = _root;
	while (cur)
	{
		// 小于往左边走
		if (key < cur->_key)
			cur = cur->_left;
		else if (key > cur->_key)
			cur = cur->_right;
		else
			return cur;
	}

	return nullptr;
}

?二叉搜索树的删除（重点）

二叉搜索树的删除相对来说会复杂一些，下面我要给大家分析一下。有四种情况先看下面这棵树，分别对以下四个节点进行删除会发生什么（如何处理）？

删除节点1时，它的左右都为空，可以直接删除
删除节点2时，它的左不为空右为空，删除方法如下：

还要分析一种特殊的情况，就是此时2没有父亲节点，也就是自己为根时，看下面如何操作

删除节点7时，它的左为为右不为空，删除方法如下：

和情况2一样，该节点如果为根节点，就让自己的右孩子变成根节点。

左右都不为空（替代法）

这种情况我们采用替代法来解决，替代法就是找一个节点和现在这个节点交换，然后转移为上面的情况，具体如下：我们可以选择用左子树的最右节点（左子树最大的节点）或右子树的最左节点（右子树的最小节点）和当前节点互换，然后删除互换后的节点，这里我们统一采用用右子树的最右节点来进行替换。

然后这里可以转化为情况3来对节点进行删除，因为所有的最左孩子一定是左为空，右是不确定的。

总结：一共有四种情况，但是情况1可以归为情况3，因为它也是左为空，所以整体处理下来是三种情况。

代码实现如下：

bool Erase(const K& key)
{
		// 如果树为空，删除失败
		if (_root == nullptr)
			return false;

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			// 小于往左边走
			if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				// 找到了，开始删除
				// 1.左右子树都为空 直接删除  可以归类为左为空
				// 2.左右子树只有一边为空  左为空，父亲指向我的右，右为空，父亲指向我的左  
				// 3.左右子树都不为空  取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
				if (cur->_left == nullptr)
				{
					// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
					// 根节点的话会导致parent为nullptr
					if (_root == cur)
					{
						_root = _root->_right;
					}
					else
					{
						// 左为空，父亲指向我的右
						// 判断cur在父亲的左还是右
						if (parent->_left == cur) // cur->_key < parent->_key
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}

					delete cur;
					cur = nullptr;
				}
				else if (cur->_right == nullptr)
				{
					if (_root == cur)
					{
						_root = _root->_left;
					}
					else
					{
						// 右为空，父亲指向我的左
						// 判断cur在父亲的左还是右
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}

					delete cur;
					cur = nullptr;
				}
				else
				{
					// 找右子树中最小的节点
					Node* rightMinParent = cur;
					Node* rightMin = cur->_right;// 去右子树找
					while (rightMin->_left)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_left;
					}
					//swap(cur->_key, rightMin->_key);
					// 替代删除
					cur->_key = rightMin->_key;

					// 转换成了第一种情况  左为空
					if (rightMinParent->_left == rightMin)
						rightMinParent->_left = rightMin->_right;
					else
						rightMinParent->_right = rightMin->_right;


					delete rightMin;
					rightMin = nullptr;
				}
				return true;
			}
		}

		return false;
	}

测试代码如下：（要测试每种情况，还有测试删空的情况）

void TestBSTree()
{
	BSTree<int> bt;
	int arr[] = { 5,3,4,1,7,8,2,6,0,9 };
	for (auto e : arr)
	{
		cout << "插入 " << e << " 后：";
		bt.Insert(e);
		bt.InOrder();
	}
	
	cout << "------------------------------" << endl;
	for (auto e : arr)
	{
		cout << "删除 " << e << " 后：";
		bt.Erase(e);
		bt.InOrder();
	}

}

代码运行结果如下：

?二叉搜索树的应用

二叉搜索树有两种模型：

K模型： K模型只有key值，节点只存储key值。这里主要应用就是查找判断某个元素在不在。
KV模型： KV模型每个key值都对应着一个value，主要应用就是通过key找value。（我们平时查找单词就是通过中文找英文，或者通过英文找中文）

下面我把上面的K模型的代码简单改造一下，实现KV模型：（这里没有使用传键值对的方法，之后的博客我会给大家介绍，这里使用传两个值的方式）

template <class K, class V>
struct BSTNode
{
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
K _key;
V _value;

BSTNode(const K& key, const V& value)
	:_left(nullptr)
	, _right(nullptr)
	, _key(key)
	,_value(value)
{}
};
template <class K, class V>
class BSTree //Binary Search Tree
{
typedef BSTNode<K, V> Node;
public:
~BSTree()
{
	Node* cur = _root;
	while (cur)
	{
		Erase(cur->_key);
		cur = _root;
	}
}
Node* Find(const K& key)
{
	if (_root == nullptr)
		return nullptr;
	Node* cur = _root;
	while (cur)
	{
		// 小于往左边走
		if (key < cur->_key)
			cur = cur->_left;
		else if (key > cur->_key)
			cur = cur->_right;
		else
			return cur;
	}

	return nullptr;
}
bool Insert(const K& key, const V& value)
{
	// 没有节点时第一个节点就是根节点
	if (_root == nullptr)
	{
		_root = new Node(key, value);
		return true;
	}

	// 用一个父亲节点记录cur的上一个节点
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		parent = cur;
		// 小于往左边走
		if (key < cur->_key)
			cur = cur->_left;
		else if (key > cur->_key)
			cur = cur->_right;
		else
			return false;// 已有的节点不插入，此次插入失败
	}

	cur = new Node(key, value);
	// 判断应该插在父节点的左边还是右边
	if (cur->_key < parent->_key)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}

	return true;
}
bool Erase(const K& key)
{
	// 如果树为空，删除失败
	if (_root == nullptr)
		return false;

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		// 小于往左边走
		if (key < cur->_key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			// 找到了，开始删除
			// 1.左右子树都为空 直接删除  可以归类为左为空
			// 2.左右子树只有一边为空  左为空，父亲指向我的右，右为空，父亲指向我的左  
			// 3.左右子树都不为空  取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
			if (cur->_left == nullptr)
			{
				// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
				// 根节点的话会导致parent为nullptr
				if (_root == cur)
				{
					_root = _root->_right;
				}
				else
				{
					// 左为空，父亲指向我的右
					// 判断cur在父亲的左还是右
					if (parent->_left == cur) // cur->_key < parent->_key
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
				}

				delete cur;
				cur = nullptr;
			}
			else if (cur->_right == nullptr)
			{
				if (_root == cur)
				{
					_root = _root->_left;
				}
				else
				{
					// 右为空，父亲指向我的左
					// 判断cur在父亲的左还是右
					if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
				}

				delete cur;
				cur = nullptr;
			}
			else
			{
				// 找右子树中最小的节点
				Node* rightMinParent = cur;
				Node* rightMin = cur->_right;// 去右子树找
				while (rightMin->_left)
				{
					rightMinParent = rightMin;
					rightMin = rightMin->_left;
				}
				//swap(cur->_key, rightMin->_key);
				// 替代删除
				cur->_key = rightMin->_key;

				// 转换成了第一种情况  左为空
				if (rightMinParent->_left == rightMin)
					rightMinParent->_left = rightMin->_right;
				else
					rightMinParent->_right = rightMin->_right;


				delete rightMin;
				rightMin = nullptr;
			}
			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 << ":" << root->_value << endl;
	_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};

void TestBSTree_KV1()
{
// 创建一个简易的字典
BSTree<string, string> dict;

dict.Insert("苹果", "apple");
dict.Insert("排序", "sort");
dict.Insert("培养", "cultivate");
dict.Insert("通过", "pass");
dict.Insert("apple", "苹果");
dict.Insert("sort", "排序");
dict.Insert("cultivate", "培养");
dict.Insert("pass", "通过");

string str;
while (cin >> str)
{
	BSTNode<string, string>* ret = dict.Find(str);
	if (ret)
	{
		cout << ret->_value << endl;
	}
	else
	{
		cout << "本字典无此词" << endl;
	}
}

下面测试几个应用：实例1 英汉字典

void TestBSTree_KV1()
	{
		// 创建一个简易的字典
		BSTree<string, string> dict;

		dict.Insert("苹果", "apple");
		dict.Insert("排序", "sort");
		dict.Insert("培养", "cultivate");
		dict.Insert("通过", "pass");
		dict.Insert("apple", "苹果");
		dict.Insert("sort", "排序");
		dict.Insert("cultivate", "培养");
		dict.Insert("pass", "通过");

		string str;
		while (cin >> str)
		{
			BSTNode<string, string>* ret = dict.Find(str);
			if (ret)
			{
				cout << ret->_value << endl;
			}
			else
			{
				cout << "本字典无此词" << endl;
			}
		}
	}

代码运行结果演示：

实例2：统计树

void TestBSTree_KV2()
{
	// 统计水果个数
	BSTree<string, int> countTree;

	string strArr[] = { "香蕉","水蜜桃","西瓜","苹果","香蕉" ,"西瓜","香蕉" ,"苹果","西瓜","苹果","苹果","香蕉" ,"水蜜桃" };

	for (auto e : strArr)
	{
		BSTNode<string, int>* ret = countTree.Find(e);
		if (ret == nullptr)
		{
			// 第一次插入
			countTree.Insert(e, 1);
		}
		else
		{
			ret->_value++;
		}
	}

	countTree.InOrder();
}

代码运行结果如下：

?二叉树性能分析

一般情况下，二叉搜索树的插入和删除的效率都是O(logN)，极端情况会导致效率变成O(N)。

理想状态：完全二叉树：O(logN)

极端情况：一条链：O(1)

后面我要和大家分析的AVL树会利用旋转，就可解决掉这种极端情况。

?总结

上面这些是二叉搜索树的大致内容，其中删除大家可以好好理解一下，它后面还有两棵树我还没有介绍，就是AVL树和红黑树，在后面两篇博客我都会介绍。今天就先到这了，喜欢的话，欢迎点赞支持~

频道导航

C++数据结构二叉搜索树的实现应用与分析

目录

?概念

?二叉搜索树的实现

?基本框架

?二叉搜索树的插入

?二叉搜索树的查找

?二叉搜索树的删除（重点）

?二叉搜索树的应用

?二叉树性能分析

?总结

您可能感兴趣的文章: