devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++数据结构 —— 二叉搜索树_定义二叉查找树的数据结构,并使用递归算法实现对二叉查找树的查找算法。

作者：我家小花儿 | 2024-03-16 00:43:39

赞

踩

定义二叉查找树的数据结构,并使用递归算法实现对二叉查找树的查找算法。

目录

1.二叉搜索树的基本概念

1.1二叉搜索树的基本特征

 2.二叉搜索树的实现

2.1数据的插入(迭代实现)

2.2数据的搜索(迭代实现)

2.3中序遍历(递归实现)

2.4数据的删除(迭代实现)

2.5数据的搜索(递归实现)

2.6数据的插入(递归实现)

2.7数据的删除(递归实现)

2.8类的完善

3.二叉搜索树的应用

4.完整代码

 二叉搜索树

1.二叉搜索树的基本概念

二叉搜索树又称二叉排序树，它可以是一颗空树。二叉搜索树的作用是搜索，排序(二叉搜索树的中序遍历是一组递增有序数据)。

1.1二叉搜索树的基本特征

如果某颗二叉树(包括空树)满足以下性质，可以作为一颗二叉搜索树：

        1.如果左子树不为空，其键值应小于根节点的键值。

        2.如果右子树不为空，其键值应大于根节点的键值。

        3.左右子树都满足上述条件。

没有二叉搜索树之前，常用的查找算法为二分查找。但是二分查找是有局限性的(必须针对有序数组)。二叉搜索树因其特性，例如我们需要查找Key值，只需要与根节点的键值做比较：若Key小于根节点的键值，则往根节点的左子树遍历；若Key值大于根节点的键值，则往根节点的右子树遍历。经计算，查找的次数等于二叉搜索树的深度。正因为如此，二叉搜索树并不是一个优秀的数据结构，因为一但碰到极端情况，二叉搜索树的搜索效率将会大打折扣。所以在往后的章节中，将会使其平衡。

 2.二叉搜索树的实现

 将二叉搜索树定义为一个类，现在将展示类的框架。往后所有的演示代码，都可以直接加入其中：

  1. // 节点
  2. template <class K>
  3. struct BST_node
  4. {
  5. 	BST_node<K>* _left;		//左子树
  6. 	BST_node<K>* _right;	//右子树
  7. 	K _key;
  8.  
  9. 	BST_node(const K& _key)
  10. 		:_key(key),_left(nullptr),_right(nullptr)
  11. 	{}
  12. };
  13.  
  14. template <class K>		//节点键值的数据类型
  15. class BST
  16. {
  17. 	typedef BST_node<K> Node;
  18. public:
  19.  
  20. private:
  21. 	Node* _root;	//根节点
  22. };

2.1数据的插入(迭代实现)

  1. bool insert(const K& key)
  2. {
  3. 	if (_root == nullptr)
  4. 	{
  5. 		_root = new Node(key);
  6. 		return true;
  7. 	}
  8. 		
  9. 	Node* prev = nullptr;	// cur的父节点
  10. 	Node* cur = _root;
  11. 	while (cur)
  12. 	{
  13. 		if (key < cur->_key)	//如果比根节点的键值小
  14. 		{
  15. 			prev = cur;
  16. 			cur = cur->_left;
  17. 		}
  18. 		else if(key > cur->_key)	//如果比根节点的键值大
  19. 		{
  20. 			prev = cur;
  21. 			cur = cur->_right;
  22. 		}
  23. 		else
  24. 		{
  25. 			// 我们不允许插入重复的数据
  26. 			return false;
  27. 		}
  28. 	}
  29.  
  30. 	// 直到遍历到空，才施行插入
  31. 	cur = new Node(key);
  32. 	if (key < prev->_key)
  33. 	{
  34. 		prev->_left = cur;
  35. 	}
  36. 	else if (key > prev->_key)
  37. 	{
  38. 		prev->_right = cur;
  39. 	}
  40. 	return true;
  41. }

2.2数据的搜索(迭代实现)

  1. bool find(const K& key)
  2. {
  3. 	if (_root == nullptr)
  4. 	{
  5. 		return false;
  6. 	}
  7. 		
  8. 	Node* cur = _root;
  9. 	while (cur)
  10. 	{
  11. 		if (key < cur->_key)
  12. 		{
  13. 			cur = cur->_left;
  14. 		}
  15. 		else if (key > cur->_key)
  16. 		{
  17. 			cur = cur->_right;
  18. 		}
  19. 		else
  20. 		{
  21. 			// 找到了
  22. 			return true;
  23. 		}
  24. 	}
  25. 	return false;
  26. }

2.3中序遍历(递归实现)

  1. void MidTraval()	//此接口作公有
  2. {
  3. 	__MidTraval(_root);
  4. 	cout << endl;
  5. }
  6.  
  7. void __MidTraval(Node* root)	//此接口做私有
  8. {
  9. 	if (root == nullptr)
  10. 	{
  11. 		return;
  12. 	}
  13.  
  14. 	__MidTraval(root->_left);
  15. 	cout << root->_key << " ";
  16. 	__MidTraval(root->_right);
  17. }

2.4数据的删除(迭代实现)

需要注意，要删除二叉搜索树的节点，就必须分两种情况讨论：

        1.要删除节点的左子树或右子树为空。

        2.要删除节点的左、右子树都不为空。

  1. bool erase(const K& key)
  2. {
  3. 	if (_root == nullptr)
  4. 	{
  5. 		return false;
  6. 	}
  7.  
  8. 	Node* prev = _root;
  9. 	Node* cur = _root;
  10. 	while (cur)
  11. 	{
  12. 		if (key < cur->_key)
  13. 		{
  14. 			prev = cur;
  15. 			cur = cur->_left;
  16. 		}
  17. 		else if (key > cur->_key)
  18. 		{
  19. 			prev = cur;
  20. 			cur = cur->_right;
  21. 		}
  22. 		else
  23. 		{
  24. 			// 如果左子树为空
  25. 			if (cur->_left == nullptr)
  26. 			{
  27. 				// 假设右子树不为空，则将右子树托孤给父节点
  28. 				if (_root == cur)
  29. 				{
  30. 					_root = _root->_right;
  31. 				}
  32. 				else if (prev->_left == cur)
  33. 				{
  34. 					prev->_left = cur->_right;
  35. 				}
  36. 				else if (prev->_right == cur)
  37. 				{
  38. 					prev->_right = cur->_right;
  39. 				}
  40.  
  41. 				delete cur;
  42. 				return true;
  43. 			}
  44.  
  45. 			// 如果右子树为空
  46. 			else if (cur->_right == nullptr)
  47. 			{
  48. 				//假设左子树不为空，则将左子树托孤给父节点
  49. 				if (_root == cur)
  50. 				{
  51. 					_root = _root->_left;
  52. 				}
  53. 				else if (prev->_left == cur)
  54. 				{
  55. 					prev->_left = cur->_left;
  56. 				}
  57. 				else if (prev->_right == cur)
  58. 				{
  59. 					prev->_right = cur->_left;
  60. 				}
  61.  
  62. 				delete cur;
  63. 				return true;
  64. 			}
  65.  
  66. 			// 如果左右子树都不为空
  67. 			else
  68. 			{
  69. 				// 假设使用右子树的最小值替代
  70. 				Node* prev = _root;
  71. 				Node* minRight = cur->_right;
  72.  
  73. 				while (minRight->_left)		//二叉树特性，越往左越小
  74. 				{
  75. 					prev = minRight;
  76. 					minRight = minRight->_left;
  77. 				}
  78.  
  79. 				cur->_key = minRight->_key;
  80.  
  81. 				// 替换好后，就要删除minRight
  82. 				if (prev->_left == minRight)
  83. 				{
  84. 					prev->_left = minRight->_right;
  85. 				}
  86. 				else if (prev->_right == minRight)
  87. 				{
  88. 					prev->_right = minRight->_right;
  89. 				}
  90. 					
  91. 				delete minRight;
  92. 				return true;
  93. 			}
  94. 		}
  95. 	}
  96. 	return false;
  97. }

2.5数据的搜索(递归实现)

  1. bool findR(const K& key)
  2. {
  3. 	return __findR(_root, key);
  4. }
  5.  
  6. bool __findR(Node* root, const K& key)	//此接口作私有
  7. {
  8. 	if (root == nullptr)
  9. 	{
  10. 		return false;
  11. 	}
  12.  
  13. 	if (key < root->_key)
  14. 	{
  15. 		return __findR(root->_left, key);
  16. 	}
  17. 	else if (key > root->_key)
  18. 	{
  19. 		return __findR(root->_right, key);
  20. 	}
  21. 	return true;
  22. }

2.6数据的插入(递归实现)

  1. bool insertR(const K& key)
  2. {
  3. 	return __insertR(_root, key);
  4. }
  5.  
  6. bool __insertR(Node*& root, const K& key)	//此接口作私有
  7. {
  8. 	if (root == nullptr)
  9. 	{
  10. 		root = new Node(key);	//注意引用传参，root相当于root->left或root->right的别名
  11. 		return true;
  12. 	}
  13.  
  14.  
  15. 	if (key < root->_key)
  16. 	{
  17. 		return __insertR(root->_left, key);
  18. 	}
  19. 	else if (key > root->_key)
  20. 	{
  21. 		return __insertR(root->_right, key);
  22. 	}
  23. 	return false;
  24. }

2.7数据的删除(递归实现)

  1. bool eraseR(const K& key)
  2. {
  3. 	return __eraseR(_root, key);
  4. }
  5.  
  6. bool __eraseR(Node*& root, const K& key)	//此接口作私有
  7. {
  8. 	if (root == nullptr)
  9. 	{
  10. 		return false;
  11. 	}
  12.  
  13. 	if (key < root->_key)
  14. 	{
  15. 		return __eraseR(root->_left, key);
  16. 	}
  17. 	else if (key > root->_key)
  18. 	{
  19. 		return __eraseR(root->_right, key);
  20. 	}
  21. 	else
  22. 	{
  23. 		Node* del = root;
  24. 		if (root->_left == nullptr)
  25. 		{
  26. 			// 此时root就是要删除的节点，并且是root的父节点的子节点的引用(root == root->_left...)
  27. 			root = root->_right;
  28.  
  29. 			delete del;
  30. 			return true;
  31. 		}
  32. 		else if (root->_right == nullptr)
  33. 		{
  34. 			root = root->_left;
  35.  
  36. 			delete del;
  37. 			return true;
  38. 		}
  39. 		else
  40. 		{
  41. 			Node* prev = _root;
  42. 			Node* minRight = root->_right;
  43.  
  44. 			while (minRight->_left)		//二叉树特性，越往左越小
  45. 			{
  46. 				prev = minRight;
  47. 				minRight = minRight->_left;
  48. 			}
  49.  
  50. 			root->_key = minRight->_key;
  51.  
  52. 			// 替换好后，就要删除minRight
  53. 			if (prev->_left == minRight)
  54. 			{
  55. 				prev->_left = minRight->_right;
  56. 			}
  57. 			else if (prev->_right == minRight)
  58. 			{
  59. 				prev->_right = minRight->_right;
  60. 			}
  61.  
  62. 			delete minRight;
  63. 			return true;
  64. 		}
  65. 	}
  66. 	return false;
  67. }

2.8类的完善

  1. BST()
  2. 	:_root(nullptr)
  3. {}
  4.  
  5. ~BST()
  6. {
  7. 	Destructor(_root);
  8. 	_root = nullptr;
  9. }
  10.  
  11. void Destructor(Node* root)	//此函数作私有
  12. {
  13. 	if (root == nullptr)
  14. 	{
  15. 		return;
  16. 	}
  17.  
  18. 	// 后序删除
  19. 	Destructor(root->_left);
  20. 	Destructor(root->_right);
  21. 	delete root;
  22. }
  23.  
  24. BST(const BST<K>& t)
  25. {
  26. 	_root = Copy(t._root);
  27. }
  28.  
  29. Node* Copy(Node* root)	//此接口作私有
  30. {
  31. 	if (root == nullptr)
  32. 	{
  33. 		return nullptr;
  34. 	}
  35.  
  36. 	Node* ret = new Node(root->_key);
  37. 	ret->_left = Copy(root->_left);
  38. 	ret->_right = Copy(root->_right);
  39. 	return ret;
  40. }
  41.  
  42. BST<K>& operator==(BST<K> t)	//现代写法
  43. {
  44. 	swap(_root, t._root);
  45. 	return *this;
  46. }

3.二叉搜索树的应用

1.K模型：

        K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。上面模拟实现的搜索就是K模型。

        例如将英文字典所有的英文单词存储二叉搜索树这个数据结构，那么可将英文单词看作关键码Key，假设我们想查找"hello"这个单词，直接去数据结构找即可。

2.KV模型：

        每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见。

        例如英汉互译，一个英文单词对应了多个汉语翻译。我们将<英文单词，中文翻译的数组>这样的键值对放入二叉搜索树中。例如查找"hello"这个单词的中文翻译，只需要查找键值对的英文单词即可。

KV模型例题：

给定下面数组，求每种水果出现的次数：

  1. string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
  2. "苹果", "香蕉", "苹果", "香蕉" };

第一步：先实现二叉搜索树(为了方便，这里只保留插入数据、查找和中序遍历的接口)：

  1. namespace KV
  2. {
  3.  
  4. 	// 节点
  5. 	template <class Key,class Val>
  6. 	struct BST_node
  7. 	{
  8. 		BST_node<Key,Val>* _left;		//左子树
  9. 		BST_node<Key,Val>* _right;	//右子树
  10. 		Key _key;
  11. 		Val _val;
  12. 		BST_node(const Key& key,const Val& val)
  13. 			:_key(key), _val(val),_left(nullptr), _right(nullptr)
  14. 		{}
  15. 	};
  16.  
  17. 	template <class Key,class Val>
  18. 	class BST
  19. 	{
  20. 		typedef BST_node<Key,Val> Node;
  21. 	public:
  22. 		bool insert(const Key& key,const Val& val)
  23. 		{
  24. 			if (_root == nullptr)
  25. 			{
  26. 				_root = new Node(key,val);
  27. 				return true;
  28. 			}
  29.  
  30. 			Node* prev = nullptr;
  31. 			Node* cur = _root;
  32. 			while (cur)
  33. 			{
  34. 				if (key < cur->_key)
  35. 				{
  36. 					prev = cur;
  37. 					cur = cur->_left;
  38. 				}
  39. 				else if (key > cur->_key)
  40. 				{
  41. 					prev = cur;
  42. 					cur = cur->_right;
  43. 				}
  44. 				else
  45. 				{
  46. 					return false;
  47. 				}
  48. 			}
  49.  
  50. 			cur = new Node(key,val);
  51. 			if (key < prev->_key)
  52. 			{
  53. 				prev->_left = cur;
  54. 			}
  55. 			else if (key > prev->_key)
  56. 			{
  57. 				prev->_right = cur;
  58. 			}
  59. 			return true;
  60. 		}
  61.  
  62.  
  63. 		Node* find(const Key& key)
  64. 		{
  65. 			if (_root == nullptr)
  66. 			{
  67. 				return nullptr;
  68. 			}
  69.  
  70. 			Node* cur = _root;
  71. 			while (cur)
  72. 			{
  73. 				if (key < cur->_key)
  74. 				{
  75. 					cur = cur->_left;
  76. 				}
  77. 				else if (key > cur->_key)
  78. 				{
  79. 					cur = cur->_right;
  80. 				}
  81. 				else
  82. 				{
  83. 					// 找到了
  84. 					return cur;
  85. 				}
  86. 			}
  87. 			return nullptr;
  88. 		}
  89.  
  90.  
  91. 		bool erase(const Key& key)
  92. 		{
  93. 			if (_root == nullptr)
  94. 			{
  95. 				return false;
  96. 			}
  97.  
  98. 			Node* prev = _root;
  99. 			Node* cur = _root;
  100. 			while (cur)
  101. 			{
  102. 				if (key < cur->_key)
  103. 				{
  104. 					prev = cur;
  105. 					cur = cur->_left;
  106. 				}
  107. 				else if (key > cur->_key)
  108. 				{
  109. 					prev = cur;
  110. 					cur = cur->_right;
  111. 				}
  112. 				else
  113. 				{
  114. 					if (cur->_left == nullptr)
  115. 					{
  116. 						if (_root == cur)
  117. 						{
  118. 							_root = _root->_right;
  119. 						}
  120. 						else if (prev->_left == cur)
  121. 						{
  122. 							prev->_left = cur->_right;
  123. 						}
  124. 						else if (prev->_right == cur)
  125. 						{
  126. 							prev->_right = cur->_right;
  127. 						}
  128.  
  129. 						delete cur;
  130. 						return true;
  131. 					}
  132.  
  133. 					else if (cur->_right == nullptr)
  134. 					{
  135. 						if (_root == cur)
  136. 						{
  137. 							_root = _root->_left;
  138. 						}
  139. 						else if (prev->_left == cur)
  140. 						{
  141. 							prev->_left = cur->_left;
  142. 						}
  143. 						else if (prev->_right == cur)
  144. 						{
  145. 							prev->_right = cur->_left;
  146. 						}
  147.  
  148. 						delete cur;
  149. 						return true;
  150. 					}
  151.  
  152. 					else
  153. 					{
  154. 						Node* prev = _root;
  155. 						Node* minRight = cur->_right;
  156.  
  157. 						while (minRight->_left)
  158. 						{
  159. 							prev = minRight;
  160. 							minRight = minRight->_left;
  161. 						}
  162.  
  163. 						cur->_key = minRight->_key;
  164. 						if (prev->_left == minRight)
  165. 						{
  166. 							prev->_left = minRight->_right;
  167. 						}
  168. 						else if (prev->_right == minRight)
  169. 						{
  170. 							prev->_right = minRight->_right;
  171. 						}
  172.  
  173. 						delete minRight;
  174. 						return true;
  175. 					}
  176. 				}
  177. 			}
  178. 			return false;
  179. 		}
  180.  
  181.  
  182. 		void MidTraval()	
  183. 		{
  184. 			__MidTraval(_root);
  185. 			cout << endl;
  186. 		}
  187.  
  188. 	private:
  189. 		Node* _root = nullptr;
  190.  
  191. 		void __MidTraval(Node* root)
  192. 		{
  193. 			if (root == nullptr)
  194. 			{
  195. 				return;
  196. 			}
  197.  
  198. 			__MidTraval(root->_left);
  199. 			cout << root->_key << ":" << root->_val << endl;
  200. 			__MidTraval(root->_right);
  201. 		}
  202. 	};
  203. }

第二步：算法实现：

  1. void test_count()
  2. {
  3. 	KV::BST<string, int> bt;
  4. 	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
  5. "苹果", "香蕉", "苹果", "香蕉" };
  6.  
  7. 	for (auto& e : arr)
  8. 	{
  9. 		KV::BST_node<string, int>* ret = bt.find(e);
  10. 		if (ret)	//不为空，证明数据结构已有
  11. 		{
  12. 			ret->_val++;	//次数++
  13. 		}
  14. 		else
  15. 		{
  16. 			bt.insert(e, 1);
  17. 		}
  18. 	}
  19.  
  20. 	bt.MidTraval();
  21. }

4.完整代码

 二叉搜索树

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/245790
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号