当前位置:主页 > 软件编程 > C代码 >

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

时间:2023-03-12 11:25:03 | 栏目:C代码 | 点击:

??博客代码已上传至gitee:https://gitee.com/byte-binxin/cpp-class-code

?概念

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

?二叉搜索树的实现

?基本框架

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

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;
};

?二叉搜索树的插入

插入分为下面几个步骤:

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

请添加图片描述

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

代码实现如下:

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();
}

代码运行结果如下:

?二叉搜索树的查找

查找的步骤如下:(和插入的步骤有些类似)

代码实现如下:

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;
}

?二叉搜索树的删除(重点)

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

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

和情况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模型的代码简单改造一下,实现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树和红黑树,在后面两篇博客我都会介绍。今天就先到这了,喜欢的话,欢迎点赞支持~

您可能感兴趣的文章:

相关文章