经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C++ » 查看文章
C++数据结构二叉搜索树的实现应用与分析
来源：jb51　　时间：2022/2/28 15:24:33　　对本文有异议

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

??概念

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

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

??二叉搜索树的实现

??基本框架

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

  1. template <class K, class V>
  2. struct BSTNode
  3. {
  4. 	BSTNode<K, V>* _left;
  5. 	BSTNode<K, V>* _right;
  6. 	K _key;
  7. 	V _value;
  8.  
  9. 	BSTNode(const K& key, const V& value)
  10. 		:_left(nullptr)
  11. 		, _right(nullptr)
  12. 		, _key(key)
  13. 		,_value(value)
  14. 	{}
  15. };
  16. template <class K, class V>
  17. class BSTree //Binary Search Tree
  18. {
  19. 	typedef BSTNode<K, V> Node;
  20. private:
  21. 	Node* _root = nullptr;
  22. };

??二叉搜索树的插入

插入分为下面几个步骤：

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

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

请添加图片描述

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

代码实现如下：

  1. bool Insert(const K& key, const V& value)
  2. {
  3. 	// 没有节点时第一个节点就是根节点
  4. 	if (_root == nullptr)
  5. 	{
  6. 		_root = new Node(key, value);
  7. 		return true;
  8. 	}
  9.  
  10. 	// 用一个父亲节点记录cur的上一个节点
  11. 	Node* parent = nullptr;
  12. 	Node* cur = _root;
  13. 	while (cur)
  14. 	{
  15. 		parent = cur;
  16. 		// 小于往左边走
  17. 		if (key < cur->_key)
  18. 			cur = cur->_left;
  19. 		else if (key > cur->_key)
  20. 			cur = cur->_right;
  21. 		else
  22. 			return false;// 已有的节点不插入，此次插入失败
  23. 	}
  24.  
  25. 	cur = new Node(key, value);
  26. 	// 判断应该插在父节点的左边还是右边
  27. 	if (cur->_key < parent->_key)
  28. 	{
  29. 		parent->_left = cur;
  30. 	}
  31. 	else
  32. 	{
  33. 		parent->_right = cur;
  34. 	}
  35.  
  36. 	return true;
  37. }

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

  1. void InOrder()
  2. {
  3. 	// 利用子函数遍历
  4. 	_InOrder(_root);
  5. 	cout << endl;
  6. }
  7. void _InOrder(Node* root)
  8. {
  9. 	if (root == nullptr)
  10. 		return;
  11.  
  12. 	_InOrder(root->_left);
  13. 	cout << root->_key << ":" << root->_value << endl;
  14. 	_InOrder(root->_right);
  15. }

测试代码如下：

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

代码运行结果如下：

??二叉搜索树的查找

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

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

代码实现如下：

  1. Node* Find(const K& key)
  2. {
  3. 	if (_root == nullptr)
  4. 		return nullptr;
  5. 	Node* cur = _root;
  6. 	while (cur)
  7. 	{
  8. 		// 小于往左边走
  9. 		if (key < cur->_key)
  10. 			cur = cur->_left;
  11. 		else if (key > cur->_key)
  12. 			cur = cur->_right;
  13. 		else
  14. 			return cur;
  15. 	}
  16.  
  17. 	return nullptr;
  18. }

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

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

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

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

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

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

  • 左右都不为空（替代法）

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

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

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

代码实现如下：

  1. bool Erase(const K& key)
  2. {
  3. 		// 如果树为空，删除失败
  4. 		if (_root == nullptr)
  5. 			return false;
  6.  
  7. 		Node* parent = nullptr;
  8. 		Node* cur = _root;
  9. 		while (cur)
  10. 		{
  11. 			// 小于往左边走
  12. 			if (key < cur->_key)
  13. 			{
  14. 				parent = cur;
  15. 				cur = cur->_left;
  16. 			}
  17. 			else if (key > cur->_key)
  18. 			{
  19. 				parent = cur;
  20. 				cur = cur->_right;
  21. 			}
  22. 			else
  23. 			{
  24. 				// 找到了，开始删除
  25. 				// 1.左右子树都为空 直接删除  可以归类为左为空
  26. 				// 2.左右子树只有一边为空  左为空，父亲指向我的右，右为空，父亲指向我的左  
  27. 				// 3.左右子树都不为空  取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
  28. 				if (cur->_left == nullptr)
  29. 				{
  30. 					// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
  31. 					// 根节点的话会导致parent为nullptr
  32. 					if (_root == cur)
  33. 					{
  34. 						_root = _root->_right;
  35. 					}
  36. 					else
  37. 					{
  38. 						// 左为空，父亲指向我的右
  39. 						// 判断cur在父亲的左还是右
  40. 						if (parent->_left == cur) // cur->_key < parent->_key
  41. 							parent->_left = cur->_right;
  42. 						else
  43. 							parent->_right = cur->_right;
  44. 					}
  45.  
  46. 					delete cur;
  47. 					cur = nullptr;
  48. 				}
  49. 				else if (cur->_right == nullptr)
  50. 				{
  51. 					if (_root == cur)
  52. 					{
  53. 						_root = _root->_left;
  54. 					}
  55. 					else
  56. 					{
  57. 						// 右为空，父亲指向我的左
  58. 						// 判断cur在父亲的左还是右
  59. 						if (parent->_left == cur)
  60. 							parent->_left = cur->_left;
  61. 						else
  62. 							parent->_right = cur->_left;
  63. 					}
  64.  
  65. 					delete cur;
  66. 					cur = nullptr;
  67. 				}
  68. 				else
  69. 				{
  70. 					// 找右子树中最小的节点
  71. 					Node* rightMinParent = cur;
  72. 					Node* rightMin = cur->_right;// 去右子树找
  73. 					while (rightMin->_left)
  74. 					{
  75. 						rightMinParent = rightMin;
  76. 						rightMin = rightMin->_left;
  77. 					}
  78. 					//swap(cur->_key, rightMin->_key);
  79. 					// 替代删除
  80. 					cur->_key = rightMin->_key;
  81.  
  82. 					// 转换成了第一种情况  左为空
  83. 					if (rightMinParent->_left == rightMin)
  84. 						rightMinParent->_left = rightMin->_right;
  85. 					else
  86. 						rightMinParent->_right = rightMin->_right;
  87.  
  88.  
  89. 					delete rightMin;
  90. 					rightMin = nullptr;
  91. 				}
  92. 				return true;
  93. 			}
  94. 		}
  95.  
  96. 		return false;
  97. 	}

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

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

代码运行结果如下：

??二叉搜索树的应用

二叉搜索树有两种模型：

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

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

  1. template <class K, class V>
  2. struct BSTNode
  3. {
  4. BSTNode<K, V>* _left;
  5. BSTNode<K, V>* _right;
  6. K _key;
  7. V _value;
  8.  
  9. BSTNode(const K& key, const V& value)
  10. 	:_left(nullptr)
  11. 	, _right(nullptr)
  12. 	, _key(key)
  13. 	,_value(value)
  14. {}
  15. };
  16. template <class K, class V>
  17. class BSTree //Binary Search Tree
  18. {
  19. typedef BSTNode<K, V> Node;
  20. public:
  21. ~BSTree()
  22. {
  23. 	Node* cur = _root;
  24. 	while (cur)
  25. 	{
  26. 		Erase(cur->_key);
  27. 		cur = _root;
  28. 	}
  29. }
  30. Node* Find(const K& key)
  31. {
  32. 	if (_root == nullptr)
  33. 		return nullptr;
  34. 	Node* cur = _root;
  35. 	while (cur)
  36. 	{
  37. 		// 小于往左边走
  38. 		if (key < cur->_key)
  39. 			cur = cur->_left;
  40. 		else if (key > cur->_key)
  41. 			cur = cur->_right;
  42. 		else
  43. 			return cur;
  44. 	}
  45.  
  46. 	return nullptr;
  47. }
  48. bool Insert(const K& key, const V& value)
  49. {
  50. 	// 没有节点时第一个节点就是根节点
  51. 	if (_root == nullptr)
  52. 	{
  53. 		_root = new Node(key, value);
  54. 		return true;
  55. 	}
  56.  
  57. 	// 用一个父亲节点记录cur的上一个节点
  58. 	Node* parent = nullptr;
  59. 	Node* cur = _root;
  60. 	while (cur)
  61. 	{
  62. 		parent = cur;
  63. 		// 小于往左边走
  64. 		if (key < cur->_key)
  65. 			cur = cur->_left;
  66. 		else if (key > cur->_key)
  67. 			cur = cur->_right;
  68. 		else
  69. 			return false;// 已有的节点不插入，此次插入失败
  70. 	}
  71.  
  72. 	cur = new Node(key, value);
  73. 	// 判断应该插在父节点的左边还是右边
  74. 	if (cur->_key < parent->_key)
  75. 	{
  76. 		parent->_left = cur;
  77. 	}
  78. 	else
  79. 	{
  80. 		parent->_right = cur;
  81. 	}
  82.  
  83. 	return true;
  84. }
  85. bool Erase(const K& key)
  86. {
  87. 	// 如果树为空，删除失败
  88. 	if (_root == nullptr)
  89. 		return false;
  90.  
  91. 	Node* parent = nullptr;
  92. 	Node* cur = _root;
  93. 	while (cur)
  94. 	{
  95. 		// 小于往左边走
  96. 		if (key < cur->_key)
  97. 		{
  98. 			parent = cur;
  99. 			cur = cur->_left;
  100. 		}
  101. 		else if (key > cur->_key)
  102. 		{
  103. 			parent = cur;
  104. 			cur = cur->_right;
  105. 		}
  106. 		else
  107. 		{
  108. 			// 找到了，开始删除
  109. 			// 1.左右子树都为空 直接删除  可以归类为左为空
  110. 			// 2.左右子树只有一边为空  左为空，父亲指向我的右，右为空，父亲指向我的左  
  111. 			// 3.左右子树都不为空  取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
  112. 			if (cur->_left == nullptr)
  113. 			{
  114. 				// 要删除节点为根节点时，直接把右子树的根节点赋值给——root
  115. 				// 根节点的话会导致parent为nullptr
  116. 				if (_root == cur)
  117. 				{
  118. 					_root = _root->_right;
  119. 				}
  120. 				else
  121. 				{
  122. 					// 左为空，父亲指向我的右
  123. 					// 判断cur在父亲的左还是右
  124. 					if (parent->_left == cur) // cur->_key < parent->_key
  125. 						parent->_left = cur->_right;
  126. 					else
  127. 						parent->_right = cur->_right;
  128. 				}
  129.  
  130. 				delete cur;
  131. 				cur = nullptr;
  132. 			}
  133. 			else if (cur->_right == nullptr)
  134. 			{
  135. 				if (_root == cur)
  136. 				{
  137. 					_root = _root->_left;
  138. 				}
  139. 				else
  140. 				{
  141. 					// 右为空，父亲指向我的左
  142. 					// 判断cur在父亲的左还是右
  143. 					if (parent->_left == cur)
  144. 						parent->_left = cur->_left;
  145. 					else
  146. 						parent->_right = cur->_left;
  147. 				}
  148.  
  149. 				delete cur;
  150. 				cur = nullptr;
  151. 			}
  152. 			else
  153. 			{
  154. 				// 找右子树中最小的节点
  155. 				Node* rightMinParent = cur;
  156. 				Node* rightMin = cur->_right;// 去右子树找
  157. 				while (rightMin->_left)
  158. 				{
  159. 					rightMinParent = rightMin;
  160. 					rightMin = rightMin->_left;
  161. 				}
  162. 				//swap(cur->_key, rightMin->_key);
  163. 				// 替代删除
  164. 				cur->_key = rightMin->_key;
  165.  
  166. 				// 转换成了第一种情况  左为空
  167. 				if (rightMinParent->_left == rightMin)
  168. 					rightMinParent->_left = rightMin->_right;
  169. 				else
  170. 					rightMinParent->_right = rightMin->_right;
  171.  
  172.  
  173. 				delete rightMin;
  174. 				rightMin = nullptr;
  175. 			}
  176. 			return true;
  177. 		}
  178. 	}
  179.  
  180. 	return false;
  181. }
  182. void InOrder()
  183. {
  184. 	// 利用子函数遍历
  185. 	_InOrder(_root);
  186. 	cout << endl;
  187. }
  188. private:
  189. void _InOrder(Node* root)
  190. {
  191. 	if (root == nullptr)
  192. 		return;
  193.  
  194. 	_InOrder(root->_left);
  195. 	cout << root->_key << ":" << root->_value << endl;
  196. 	_InOrder(root->_right);
  197. }
  198. private:
  199. Node* _root = nullptr;
  200. };
  201.  
  202. void TestBSTree_KV1()
  203. {
  204. // 创建一个简易的字典
  205. BSTree<string, string> dict;
  206.  
  207. dict.Insert("苹果", "apple");
  208. dict.Insert("排序", "sort");
  209. dict.Insert("培养", "cultivate");
  210. dict.Insert("通过", "pass");
  211. dict.Insert("apple", "苹果");
  212. dict.Insert("sort", "排序");
  213. dict.Insert("cultivate", "培养");
  214. dict.Insert("pass", "通过");
  215.  
  216. string str;
  217. while (cin >> str)
  218. {
  219. 	BSTNode<string, string>* ret = dict.Find(str);
  220. 	if (ret)
  221. 	{
  222. 		cout << ret->_value << endl;
  223. 	}
  224. 	else
  225. 	{
  226. 		cout << "本字典无此词" << endl;
  227. 	}
  228. }

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

  1. void TestBSTree_KV1()
  2. 	{
  3. 		// 创建一个简易的字典
  4. 		BSTree<string, string> dict;
  5.  
  6. 		dict.Insert("苹果", "apple");
  7. 		dict.Insert("排序", "sort");
  8. 		dict.Insert("培养", "cultivate");
  9. 		dict.Insert("通过", "pass");
  10. 		dict.Insert("apple", "苹果");
  11. 		dict.Insert("sort", "排序");
  12. 		dict.Insert("cultivate", "培养");
  13. 		dict.Insert("pass", "通过");
  14.  
  15. 		string str;
  16. 		while (cin >> str)
  17. 		{
  18. 			BSTNode<string, string>* ret = dict.Find(str);
  19. 			if (ret)
  20. 			{
  21. 				cout << ret->_value << endl;
  22. 			}
  23. 			else
  24. 			{
  25. 				cout << "本字典无此词" << endl;
  26. 			}
  27. 		}
  28. 	}

代码运行结果演示：

实例2： 统计树

  1. void TestBSTree_KV2()
  2. {
  3. 	// 统计水果个数
  4. 	BSTree<string, int> countTree;
  5.  
  6. 	string strArr[] = { "香蕉","水蜜桃","西瓜","苹果","香蕉" ,"西瓜","香蕉" ,"苹果","西瓜","苹果","苹果","香蕉" ,"水蜜桃" };
  7.  
  8. 	for (auto e : strArr)
  9. 	{
  10. 		BSTNode<string, int>* ret = countTree.Find(e);
  11. 		if (ret == nullptr)
  12. 		{
  13. 			// 第一次插入
  14. 			countTree.Insert(e, 1);
  15. 		}
  16. 		else
  17. 		{
  18. 			ret->_value++;
  19. 		}
  20. 	}
  21.  
  22. 	countTree.InOrder();
  23. }

代码运行结果如下：

??二叉树性能分析

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

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

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

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

??总结

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

到此这篇关于C++数据结构二叉搜索树的实现应用与分析的文章就介绍到这了,更多相关C++ 二叉搜索树内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue！

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C++热门文章

  • C/C++编程笔记：编写不会在C ++中编译的C程序，我教你呀！
  • 洛谷 P2085 最小函数值
  • 使用C++界面框架ImGUI开发一个简单程序
  • C++ Json解析CJsonObject的详细使用
  • C++编译错误杂记
  • 二分法（二）：采用二分法解决“最小化最大值问题”
  • C++实现json字符串与map的转换
  • C++借助curses库实现俄罗斯方块
  • 长乐培训Day5
  • 【OpenFOAM】——OpenFOAM入门算例学习

    • C++推荐文章

  • #8. 「模板」树链剖分
  • 预设型 DP
  • Standard Template Libary or C++ Standard Library
  • 一种优秀的虚拟机内存架构 - AQ
  • 如何让 MGR 不从 Primary 节点克隆数据？
  • TLScanary：Pwn中的利器
  • c++临时对象导致的生命周期问题
  • C++(Qt)-GIS开发-简易瓦片地图下载器
  • 逆向通达信 x 逆向微信 x 逆向Qt
  • C++面向对象

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号