• 二叉搜索树

    目录

    一.概念

    二.基本操作

    1.建树

    2.查找元素

    3.插入元素

    4.删除元素

    5.遍历

    三.K模型与KV模型实现

    K模型模拟实现

    KV模型模拟实现

    测试函数

    一.概念

    二叉搜索树，若其不是空树测具有以下性质:

    • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
    • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
    • 它的左右子树也分别为二叉搜索树

    因其中序遍历的结果是有序的，故也称为二叉排序树

    二.基本操作

    1.建树

    使用模板建树，泛化使用范围。

    1. namespace key
    2. {
    3. 	template<class K>
    4. 	struct BSTreeNode
    5. 	{
    6. 		BSTreeNode* _left;
    7. 		BSTreeNode* _right;
    8. 		K _key;
    9.  
    10. 		BSTreeNode(const K& key)
    11. 			:_left(nullptr)
    12. 			, _right(nullptr)
    13. 			, _key(key)
    14. 		{ }
    15. 	};
    16.  
    17.     template<class K>
    18. 	class BSTree
    19. 	{
    20. 		typedef BSTreeNode Node;
    21.  
    22.     private:
    23.         Node* _root = nullptr;
    24.     }
    25. }

    2.查找元素

    思路：因为二叉搜索树满足如上性质，所以对于每个节点， 其左子树都比它小， 右子树都比它大。所以查找元素比当前节点值大就往右走，比当前节点值小就往左走。

    1.   		bool Find(const K& key)
    2. 		{
    3.             //从根节点开始搜
    4. 			Node* cur = _root;
    5. 			
    6. 			//搜到底部
    7. 			while (cur)
    8. 			{
    9. 				if (cur->_key < key)
    10. 				{
    11. 					cur = cur->_right;
    12. 				}
    13. 				else if (cur->_key > key)
    14. 				{
    15. 					cur = cur->_left;
    16. 				}
    17. 				else
    18. 				{
    19. 					//相等了
    20. 					return true;
    21. 				}
    22. 			}
    23. 			return false;
    24. 		}

    3.插入元素

    思路：如果是空树的话直接赋值给root建树，当插入元素比当前节点值小时，往左走； 当插入元素比当前节点值大时，往右走。因其为无向图，我们应加入一个parent节点来记录当前节点（cur节点）前的位置。

    注意：

    1.因为二叉搜索树中不能有重复值，所以注意判重。

    2.插入元素时不需要挪动其他节点，遍历到底即可。

    1. 		bool Insert(const K& key)
    2. 		{
    3. 			if (_root == nullptr)
    4. 			{
    5. 				_root = new Node(key);
    6. 				return true;
    7. 			}
    8.  
    9. 			//遍历到底部
    10. 			
    11. 			Node* parent = nullptr;
    12. 			Node* cur = _root;
    13. 			while (cur)
    14. 			{
    15. 				if (cur->_key < key)
    16. 				{
    17. 					parent = cur;
    18. 					cur = cur->_right;
    19. 				}
    20. 				else if (cur->_key > key)
    21. 				{
    22. 					parent = cur;
    23. 					cur = cur->_left;
    24. 				}
    25. 				else
    26. 				{
    27. 					return false;
    28. 				}
    29. 			}
    30.  
    31. 			//到底部之后 加入树
    32. 			cur = new Node(key);
    33. 			if (parent->_key < key)
    34. 			{
    35. 				parent->_right = cur;
    36. 			}
    37. 			else
    38. 			{
    39. 				parent->_left = cur;
    40. 			}
    41.  
    42. 			return true;
    43. 		}

    4.删除元素

    删除元素是二叉搜索树的难点 观察开头给出的例图

    不难若删除一个节点 其有三种情况(删除的节点左右都为空的情况涵盖在了前两种)

    1.删除的节点左子树为空   如图中值为1的节点

    2.删除的节点右子树为空   如图中值为6的节点

    3.删除的节点左右子树都不为空  如图中值为14、3的节点

    下面对以上情况逐一进行讨论

    对于每个节点，其左子树都小于自己，其右子树都大于自己。

    1.若删除的节点的左子树为空，则使其父节点的指向该节点的 right，若该节点位于其父节点的左侧，则使父节点的left 指向该节点的 right，若在右侧，则使父节点的right 指向该节点的 right。

    2.若删除的节点的右子树为空，则使其父节点的指向该节点的 left，若该节点位于其父节点的左侧，则使父节点的left 指向该节点的 left，若在右侧，则使父节点的right 指向该节点的 left。

    3.若删除的节点左右子树都不为空

    采用替换法删除：

    基于搜索二叉树的性质 我们需要找到右子树的最小节点或左子树的最大节点来替换要删除的节点，再将这个找到的节点的子树继承给其父节点，即保证删除后仍然满足对于每个节点，其左子树都小于自己，其右子树都大于自己。

    注意：

    若删除的节点类似元素8， 其右子树

    的最小节点就是其右节点，需要特判。

    1. 		bool Erase(const K& key)
    2. 		{
    3. 			//删除有三种情况 
    4. 			//1 删除的节点的左为空
    5. 			//2 删除的节点的右为空
    6. 			//3 删除的节点左右都空 ---> 替换删除法
    7. 			//即找左子树的最右节点(最大值) 或 右子树的最左节点代替即可
    8. 			//下即 右子树的最左节点
    9. 			Node* parent = nullptr;
    10. 			Node* cur = _root;
    11.  
    12. 			while (cur)
    13. 			{
    14. 				if (cur->_key < key)
    15. 				{
    16. 					parent = cur;
    17. 					cur = cur->_right;
    18. 				}
    19. 				else if (cur->_key > key)
    20. 				{
    21. 					parent = cur;
    22. 					cur = cur->_right;
    23. 				}
    24. 				else
    25. 				{
    26. 					//相等删除
    27. 					//1 左为空 父亲指向我的右
    28. 					if (cur->_left == nullptr)
    29. 					{
    30. 						if (cur == _root)
    31. 						{
    32. 							_root = cur->_right;
    33. 						}
    34. 						else
    35. 						{
    36. 							// 看它是 父亲的左节点 还是右节点
    37. 							if (cur == parent->_left)
    38. 							{
    39. 								parent->_left = cur->_right;
    40. 							}
    41. 							else
    42. 							{
    43. 								parent->_right = cur->_right;
    44. 							}
    45. 						}
    46. 						
    47. 						// 终止条件 防止内存泄漏
    48. 						delete cur;
    49. 					}
    50. 					//2 右为空 父亲指向我的左
    51. 					else if (cur->_right == nullptr)
    52. 					{
    53. 						if (cur == _root)
    54. 						{
    55. 							_root = cur->_left;
    56. 						}
    57. 						else
    58. 						{
    59. 							if (cur == parent->_left)
    60. 							{
    61. 								parent->_left = cur->_left;
    62. 							}
    63. 							else
    64. 							{
    65. 								parent->_right = cur->_left;
    66. 							}
    67. 						}
    68. 						delete cur;
    69. 					}
    70. 					//3 左右都不为空 找右子树的最小值替换
    71. 					else
    72. 					{
    73. 						Node* RightMinParent = cur;
    74. 						Node* RightMin = cur->_right;
    75. 						while (RightMin->_left)
    76. 						{
    77. 							RightMinParent = RightMin;
    78. 							RightMin = RightMin->_left;
    79. 						}
    80.  
    81. 						swap(cur->_key, RightMin->_key);
    82. 						//两种情况
    83. 						//1.一开始的rightmin 有左子树 把他的右子树给父亲的左边
    84. 						//2.一开始的rightmin 没有左子树
    85. 					
    86. 						if (RightMinParent->_left == RightMin)
    87. 						{
    88. 							RightMinParent->_left = RightMin->_right;
    89.  
    90. 						}
    91. 						else
    92. 						{
    93. 							RightMinParent->_right = RightMin->_right;
    94. 						}
    95.  
    96. 						delete RightMin;
    97. 					}
    98.  
    99. 					//成功删除
    100. 					return true;
    101. 				}
    102. 			}
    103. 			return false;
    104. 		}

    5.遍历

    中序遍历按 左子树 根 右子树 的循序走即可

    1. 		void _InOrder(Node* root)
    2. 		{
    3. 			if (root == nullptr)
    4. 				return;
    5.  
    6. 			_InOrder(root->_left);
    7. 			cout << root->_key << ' ';
    8. 			_InOrder(root->_right);
    9. 		}

    三.K模型与KV模型实现

    1.K模型:K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
    的值。
    比如:给一个单词word，判断该单词是否拼写正确，具体方式如下

    • 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
    • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

    2.KV模型:每一个关键码key，都有与之对应的值Value，即的键值对。该种方
    式在现实生活中非常常见:

    • 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对;
    • 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。

    K模型模拟实现

    1. namespace key
    2. {
    3. 	//BS节点
    4. 	template<class K>
    5. 	struct BSTreeNode
    6. 	{
    7. 		BSTreeNode* _left;
    8. 		BSTreeNode* _right;
    9. 		K _key;
    10.  
    11. 		BSTreeNode(const K& key)
    12. 			:_left(nullptr)
    13. 			, _right(nullptr)
    14. 			, _key(key)
    15. 		{ }
    16. 	};
    17.  
    18. 	template<class K>
    19. 	class BSTree
    20. 	{
    21. 		typedef BSTreeNode Node;
    22.  
    23. 	public:
    24.  
    25. 		bool Insert(const K& key)
    26. 		{
    27. 			//搜索树不会平衡 一直延伸即可 不会替换
    28. 			if (_root == nullptr)
    29. 			{
    30. 				_root = new Node(key);
    31. 				return true;
    32. 			}
    33.  
    34. 			//遍历到底部
    35. 			
    36. 			Node* parent = nullptr;
    37. 			Node* cur = _root;
    38. 			while (cur)
    39. 			{
    40. 				if (cur->_key < key)
    41. 				{
    42. 					parent = cur;
    43. 					cur = cur->_right;
    44. 				}
    45. 				else if (cur->_key > key)
    46. 				{
    47. 					parent = cur;
    48. 					cur = cur->_left;
    49. 				}
    50. 				else
    51. 				{
    52. 					return false;
    53. 				}
    54. 			}
    55.  
    56. 			//到底部之后
    57. 			cur = new Node(key);
    58. 			if (parent->_key < key)
    59. 			{
    60. 				parent->_right = cur;
    61. 			}
    62. 			else
    63. 			{
    64. 				parent->_left = cur;
    65. 			}
    66.  
    67. 			return true;
    68. 		}
    69.  
    70. 		bool Find(const K& key)
    71. 		{
    72. 			Node* cur = _root;
    73. 			
    74. 			//搜到底部
    75. 			while (cur)
    76. 			{
    77. 				if (cur->_key < key)
    78. 				{
    79. 					cur = cur->_right;
    80. 				}
    81. 				else if (cur->_key > key)
    82. 				{
    83. 					cur = cur->_left;
    84. 				}
    85. 				else
    86. 				{
    87. 					//  相等了
    88. 					return true;
    89. 				}
    90. 			}
    91. 			return false;
    92. 		}
    93.  
    94. 		bool Erase(const K& key)
    95. 		{
    96. 			//删除有三种情况 
    97. 			//1 删除的节点的左为空
    98. 			//2 删除的节点的右为空
    99. 			//3 删除的节点左右都空 ---> 替换删除法
    100. 			//即找左子树的最右节点(最大值) 或 右子树的最左节点代替即可
    101. 			//下即 右子树的最左节点
    102. 			Node* parent = nullptr;
    103. 			Node* cur = _root;
    104.  
    105. 			while (cur)
    106. 			{
    107. 				if (cur->_key < key)
    108. 				{
    109. 					parent = cur;
    110. 					cur = cur->_right;
    111. 				}
    112. 				else if (cur->_key > key)
    113. 				{
    114. 					parent = cur;
    115. 					cur = cur->_right;
    116. 				}
    117. 				else
    118. 				{
    119. 					//相等删除
    120. 					//1 左为空 父亲指向我的右
    121. 					if (cur->_left == nullptr)
    122. 					{
    123. 						if (cur == _root)
    124. 						{
    125. 							_root = cur->_right;
    126. 						}
    127. 						else
    128. 						{
    129. 							// 看它是 父亲的左节点 还是右节点
    130. 							if (cur == parent->_left)
    131. 							{
    132. 								parent->_left = cur->_right;
    133. 							}
    134. 							else
    135. 							{
    136. 								parent->_right = cur->_right;
    137. 							}
    138. 						}
    139. 						
    140. 						// 终止条件 防止内存泄漏
    141. 						delete cur;
    142. 					}
    143. 					//2 右为空 父亲指向我的左
    144. 					else if (cur->_right == nullptr)
    145. 					{
    146. 						if (cur == _root)
    147. 						{
    148. 							_root = cur->_left;
    149. 						}
    150. 						else
    151. 						{
    152. 							if (cur == parent->_left)
    153. 							{
    154. 								parent->_left = cur->_left;
    155. 							}
    156. 							else
    157. 							{
    158. 								parent->_right = cur->_left;
    159. 							}
    160. 						}
    161. 						delete cur;
    162. 					}
    163. 					//3 左右都不为空 找右子树的最小值替换
    164. 					else
    165. 					{
    166. 						Node* RightMinParent = cur;
    167. 						Node* RightMin = cur->_right;
    168. 						while (RightMin->_left)
    169. 						{
    170. 							RightMinParent = RightMin;
    171. 							RightMin = RightMin->_left;
    172. 						}
    173.  
    174. 						swap(cur->_key, RightMin->_key);
    175. 						//两种情况
    176. 						//1.一开始的rightmin 有左子树 把他的右子树给父亲的左边
    177. 						//2.一开始的rightmin 没有左子树
    178. 					
    179. 						if (RightMinParent->_left == RightMin)
    180. 						{
    181. 							RightMinParent->_left = RightMin->_right;
    182.  
    183. 						}
    184. 						else
    185. 						{
    186. 							RightMinParent->_right = RightMin->_right;
    187. 						}
    188.  
    189. 						delete RightMin;
    190. 					}
    191.  
    192. 					//成功删除
    193. 					return true;
    194. 				}
    195. 			}
    196. 			return false;
    197. 		}
    198.  
    199. 		void InOrder()
    200. 		{
    201. 			_InOrder(_root);
    202. 			cout << endl;
    203.  
    204. 		}
    205.  
    206. 	private:
    207.  
    208. 		void _InOrder(Node* root)
    209. 		{
    210. 			if (root == nullptr)
    211. 				return;
    212.  
    213. 			_InOrder(root->_left);
    214. 			cout << root->_key << ' ';
    215. 			_InOrder(root->_right);
    216. 		}
    217. 		Node* _root = nullptr;
    218. 	};
    219.  
    220. };

    kv模型笔者不再赘述，原理相同，请读者自行理解。

    KV模型模拟实现

    1. namespace key_value
    2. {
    3. 	//BS节点
    4. 	template<class K, class V>
    5. 	struct BSTreeNode
    6. 	{
    7. 		BSTreeNode* _left;
    8. 		BSTreeNode* _right;
    9. 		K _key;
    10. 		V _value;
    11.  
    12. 		BSTreeNode(const K& key, const V& value)
    13. 			:_left(nullptr)
    14. 			, _right(nullptr)
    15. 			, _key(key)
    16. 			,_value(value)
    17. 		{ }
    18. 	};
    19.  
    20. 	template<class K, class V>
    21. 	class BSTree
    22. 	{
    23. 		typedef BSTreeNode Node;
    24. 	public:
    25.  
    26. 		bool Insert(const K& key, const V& value)
    27. 		{
    28. 			//搜索树不会平衡 一直延伸即可 不会替换
    29. 			if (_root == nullptr)
    30. 			{
    31. 				_root = new Node(key, value);
    32. 				return true;
    33. 			}
    34.  
    35. 			//遍历到底部
    36.  
    37. 			Node* parent = nullptr;
    38. 			Node* cur = _root;
    39. 			while (cur)
    40. 			{
    41. 				if (cur->_key < key)
    42. 				{
    43. 					parent = cur;
    44. 					cur = cur->_right;
    45. 				}
    46. 				else if (cur->_key > key)
    47. 				{
    48. 					parent = cur;
    49. 					cur = cur->_left;
    50. 				}
    51. 				else
    52. 				{
    53. 					return false;
    54. 				}
    55. 			}
    56.  
    57. 			//到底部之后
    58. 			cur = new Node(key, value);
    59. 			if (parent->_key < key)
    60. 			{
    61. 				parent->_right = cur;
    62. 			}
    63. 			else
    64. 			{
    65. 				parent->_left = cur;
    66. 			}
    67.  
    68. 			return true;
    69. 		}
    70. 		// find 改为返回节点
    71. 		Node* Find(const K& key)
    72. 		{
    73. 			Node* cur = _root;
    74.  
    75. 			//搜到底部
    76. 			while (cur)
    77. 			{
    78. 				if (cur->_key < key)
    79. 				{
    80. 					cur = cur->_right;
    81. 				}
    82. 				else if (cur->_key > key)
    83. 				{
    84. 					cur = cur->_left;
    85. 				}
    86. 				else
    87. 				{
    88. 					//  相等了
    89. 					return cur;
    90. 				}
    91. 			}
    92. 			// 返回空节点
    93. 			return cur;
    94. 		}
    95.  
    96. 		bool Erase(const K& key)
    97. 		{
    98. 			//删除有三种情况 
    99. 			//1 删除的节点的左为空
    100. 			//2 删除的节点的右为空
    101. 			//3 删除的节点左右都空 ---> 替换删除法
    102. 			//即找左子树的最右节点(最大值) 或 右子树的最左节点代替即可
    103. 			//下即 右子树的最左节点
    104. 			Node* parent = nullptr;
    105. 			Node* cur = _root;
    106.  
    107. 			while (cur)
    108. 			{
    109. 				if (cur->_key < key)
    110. 				{
    111. 					parent = cur;
    112. 					cur = cur->_right;
    113. 				}
    114. 				else if (cur->_key > key)
    115. 				{
    116. 					parent = cur;
    117. 					cur = cur->_right;
    118. 				}
    119. 				else
    120. 				{
    121. 					//相等删除
    122. 					//1 左为空 父亲指向我的右
    123. 					if (cur->_left == nullptr)
    124. 					{
    125. 						if (cur == _root)
    126. 						{
    127. 							_root = cur->_right;
    128. 						}
    129. 						else
    130. 						{
    131. 							// 看它是 父亲的左节点 还是右节点
    132. 							if (cur == parent->_left)
    133. 							{
    134. 								parent->_left = cur->_right;
    135. 							}
    136. 							else
    137. 							{
    138. 								parent->_right = cur->_right;
    139. 							}
    140. 						}
    141.  
    142. 						// 终止条件 防止内存泄漏
    143. 						delete cur;
    144. 					}
    145. 					//2 右为空 父亲指向我的左
    146. 					else if (cur->_right == nullptr)
    147. 					{
    148. 						if (cur == _root)
    149. 						{
    150. 							_root = cur->_left;
    151. 						}
    152. 						else
    153. 						{
    154. 							if (cur == parent->_left)
    155. 							{
    156. 								parent->_left = cur->_left;
    157. 							}
    158. 							else
    159. 							{
    160. 								parent->_right = cur->_left;
    161. 							}
    162. 						}
    163. 						delete cur;
    164. 					}
    165. 					//3 左右都不为空 找右子树的最小值替换
    166. 					else
    167. 					{
    168. 						Node* RightMinParent = cur;
    169. 						Node* RightMin = cur->_right;
    170. 						while (RightMin->_left)
    171. 						{
    172. 							RightMinParent = RightMin;
    173. 							RightMin = RightMin->_left;
    174. 						}
    175.  
    176. 						swap(cur->_key, RightMin->_key);
    177. 						//两种情况
    178. 						//1.一开始的rightmin 有左子树 把他的右子树给父亲的左边
    179. 						//2.一开始的rightmin 没有左子树
    180.  
    181. 						if (RightMinParent->_left == RightMin)
    182. 						{
    183. 							RightMinParent->_left = RightMin->_right;
    184.  
    185. 						}
    186. 						else
    187. 						{
    188. 							RightMinParent->_right = RightMin->_right;
    189. 						}
    190.  
    191. 						delete RightMin;
    192. 					}
    193.  
    194. 					//成功删除
    195. 					return true;
    196. 				}
    197. 			}
    198. 			return false;
    199. 		}
    200.  
    201. 		void InOrder()
    202. 		{
    203. 			_InOrder(_root);
    204. 			cout << endl;
    205.  
    206. 		}
    207.  
    208. 	private:
    209.  
    210. 		void _InOrder(Node* root)
    211. 		{
    212. 			if (root == nullptr)
    213. 				return;
    214.  
    215. 			_InOrder(root->_left);
    216. 			cout << root->_key << ":" << root->_value << endl;
    217. 			_InOrder(root->_right);
    218. 		}
    219.  
    220. 		Node* _root = nullptr;
    221. 	};
    222.  
    223.  
    224.  
    225. };

    测试函数

    最后留下三组测试函数：

    k模型

    1. 	void TestBSTree1()
    2. 	{
    3. 		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    4. 		BSTree<int> t1;
    5. 		for (auto e : a)
    6. 		{
    7. 			t1.Insert(e);
    8. 		}
    9.  
    10. 		t1.InOrder();
    11.  
    12. 		cout << endl;
    13. 		//t1.Erase(3);
    14. 		t1.Erase(8);
    15.  
    16. 		t1.InOrder();
    17.  
    18. 		for (auto e : a)
    19. 		{
    20. 			t1.Erase(e);
    21. 			t1.InOrder();
    22. 		}
    23. 	}

    kv模型

    1.  
    2.  
    3. 	void TestBSTree2()
    4. 	{
    5. 		BSTree dict;
    6. 		dict.Insert("string", "字符串");
    7. 		dict.Insert("left", "左边");
    8. 		dict.Insert("insert", "插入");
    9. 		//...
    10.  
    11. 		string str;
    12. 		while (cin >> str)
    13. 		{
    14. 			BSTreeNode* ret = dict.Find(str);
    15. 			if (ret)
    16. 			{
    17. 				cout << ret->_value << endl;
    18. 			}
    19. 			else
    20. 			{
    21. 				cout << "无此单词，请重新输入" << endl;
    22. 			}
    23. 		}
    24. 	}
    25.  
    26.  
    27. 	void TestBSTree3()
    28. 	{
    29. 		// 统计次数
    30. 		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
    31. "苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
    32. 		BSTreeint> countTree;
    33. 		for (const auto& str : arr)
    34. 		{
    35. 			auto ret = countTree.Find(str);
    36. 			if (ret == nullptr)
    37. 			{
    38. 				countTree.Insert(str, 1);
    39. 			}
    40. 			else
    41. 			{
    42. 				ret->_value++;
    43. 			}
    44. 		}
    45.  
    46. 		countTree.InOrder();
    47. 	}

  • 相关阅读:
    华为机试真题 C++ 实现【字符串重新排列】【2022.11 Q4新题】
    shiro-反序列化漏洞
    低代码平台技术分享官 | 漫话iGIX前端设计模式
    多维分析预汇总应该怎样做才管用？
    jenkins自动化部署安装
    CDH集群集成外部Flink（改进版-与时俱进）
    TypeScript学习总结（一）
    【PyTorch深度学习项目实战100例】—— 基于RNN实现垃圾邮件辨别 | 第57例
    都说 C++ 没有 GC，RAII: 那么我算个啥？
    线上环境建设，要扛得住真刀真枪的考验
  • 原文地址：https://blog.csdn.net/Xiang2992/article/details/139422643