• C++搜索二叉树

    一、搜索二叉树概念

    搜索二叉树是一种树形结构，常用于map当中。搜索二叉树严格遵守左小右大的规则

    C语言中实现搜索二叉树有一些困难，并且在面对一些特定题目实现较困难。因此采用C++的方式再次实现搜索二叉树

    二、搜索二叉树的实现

    插入

     搜索二叉树在插入之前必须要先遍历查找到合适的位置，再找到合适的位置后将结点插入。这里需要考虑如何将插入节点与原二叉树连接，因此需要同时记录父节点以方便连接

    1. 	bool Insert(const K& key)
    2. 	{
    3. 		if (_root == nullptr)
    4. 		{
    5. 			_root = new Node(key);
    6. 			return true;
    7. 		}
    8. 		Node* parent = nullptr;
    9. 		Node* cur = _root;
    10. 		while (cur)
    11. 		{
    12. 			if (cur->_key < key)
    13. 			{
    14. 				parent = cur;
    15. 				cur = cur->_right;
    16. 			}
    17. 			else if (cur->_key > key)
    18. 			{
    19. 				parent = cur;
    20. 				cur = cur->_left;
    21. 			}
    22. 			else
    23. 			{
    24. 				return false;
    25. 			}
    26. 		}
    27. 		//将插入节点与树连接
    28. 		cur = new Node(key);
    29. 		if (parent->_key < key)
    30. 		{
    31. 			parent->_right = cur;
    32. 		}
    33. 		else
    34. 		{
    35. 			parent->_left = cur;
    36. 		}
    37. 		return true;
    38. 	}

    删除

    删除需要考虑的情况比插入更复杂：

    ①在叶子节点删除

    下图中4、6、10都是叶子节点，删除叶子节点的处理比较简单，直接删除即可

    ②删除有左孩子或者有右孩子的节点

    寻找删除节点的父节点，继承删除节点的子节点

    这里需要考虑删除根节点的问题，如果根节点只有单一子树，由于根节点并没有父节点，会出现空指针问题

    因此如果删除节点为根节点，并且根节点只有单一子树，则更新根节点（采用替代法也可以，但是更新根节点更简单）

    ③删除同时有左孩子和右孩子的节点

    只能间接删除，同时有两个孩子，就只能采用替代法。选择删除节点左子树上的最大节点或者右子树上的最小节点替代该节点，因为需要保持左小右大的规则

    1. 	bool Erase(const K& key)
    2. 	{
    3. 		Node* parent = nullptr;
    4. 		Node* cur = _root;
    5.  
    6. 		while (cur)
    7. 		{
    8. 			if (cur->_key < key)
    9. 			{
    10. 				parent = cur;
    11. 				cur = cur->_right;
    12. 			}
    13. 			else if (cur->_key > key)
    14. 			{
    15. 				parent = cur;
    16. 				cur = cur->_left;
    17. 			}
    18. 			else
    19. 			{
    20. 				if(cur->_left==nullptr)//单个孩子左为空
    21. 				{
    22. 					if (cur == _root)
    23. 					{
    24. 						_root = cur->_right;
    25. 					}
    26. 					else
    27. 					{
    28. 						if (parent->_left == cur)
    29. 						{
    30. 							parent->_left = cur->_right;
    31. 						}
    32. 						else
    33. 						{
    34. 							parent->_right = cur->_right;
    35. 						}
    36. 					}
    37. 					delete cur;
    38. 				}
    39. 				else if(cur->_right==nullptr)//单个孩子右为空
    40. 				{
    41. 					if (cur == _root)
    42. 					{
    43. 						_root = cur->_left;
    44. 						//如果删除根节点，由于根节点没有父节点，因此直接更新根节点
    45. 					}
    46. 					else
    47. 					{
    48. 						if (parent->_left == cur)
    49. 						{
    50. 							parent->_left = cur->_left;
    51. 						}
    52. 						else
    53. 						{
    54. 							parent->_right = cur->_left;
    55. 						}
    56. 					}
    57. 					delete cur;
    58. 				}
    59. 				else//同时有两个孩子
    60. 				{
    61. 					//找要删除节点的右树最小节点或左树最大节点替代
    62. 					Node* minRight = cur->_right;//右树最小
    63. 					Node* pminRight = cur;//minRight的父节点
    64. 					//这里不赋值为nullptr也是考虑到如果删除根节点的空指针问题
    65. 					while (minRight->_left)//最小需要往左找
    66. 					{
    67. 						pminRight = minRight;
    68. 						minRight = minRight->_left;
    69. 					}
    70. 					cur->_key = minRight->_key;//替代
    71. 					//pminRight->_left = minRight->_right;对于根节点会有空指针问题
    72. 					if (pminRight->_left == minRight)//考虑根节点删除问题
    73. 					{
    74. 						pminRight->_left = minRight->_right;
    75. 					}
    76. 					else
    77. 					{
    78. 						pminRight->_right = minRight->_right;
    79. 					}	
    80. 					delete minRight;
    81. 				}
    82. 				return true;
    83. 			}
    84. 		}
    85. 		return false;
    86. 	}

    整体实现

    1. #pragma once
    2. #include
    3. using namespace std;
    4.  
    5.  
    6. template<class K>
    7. struct BSTreeNode
    8. {
    9. 	BSTreeNode* _right;
    10. 	BSTreeNode* _left;
    11. 	K _key;
    12.  
    13. 	BSTreeNode(const K& key)
    14. 		:_left(nullptr),_right(nullptr),_key(key)
    15. 	{}
    16. };
    17.  
    18. template<class K>
    19. class BSTree
    20. {
    21. 	typedef BSTreeNode Node;
    22. public:
    23.  
    24.  
    25. 	BSTree() = default;//强制生成默认构造
    26. 	BSTree(const BSTree& t)//拷贝构造
    27. 	{
    28. 		_root = Copy(t._root);
    29. 	}
    30. 	BSTree& operator=(BSTree t)//赋值构造
    31. 	{
    32. 		swap(_root, t._root);
    33. 		return *this;
    34. 	}
    35. 	~BSTree()
    36. 	{
    37. 		Destory(_root);
    38. 	}
    39.  
    40. 	bool Insert(const K& key)
    41. 	{
    42. 		if (_root == nullptr)
    43. 		{
    44. 			_root = new Node(key);
    45. 			return true;
    46. 		}
    47. 		Node* parent = nullptr;
    48. 		Node* cur = _root;
    49. 		while (cur)
    50. 		{
    51. 			if (cur->_key < key)
    52. 			{
    53. 				parent = cur;
    54. 				cur = cur->_right;
    55. 			}
    56. 			else if (cur->_key > key)
    57. 			{
    58. 				parent = cur;
    59. 				cur = cur->_left;
    60. 			}
    61. 			else
    62. 			{
    63. 				return false;
    64. 			}
    65. 		}
    66. 		//将插入节点与树连接
    67. 		cur = new Node(key);
    68. 		if (parent->_key < key)
    69. 		{
    70. 			parent->_right = cur;
    71. 		}
    72. 		else
    73. 		{
    74. 			parent->_left = cur;
    75. 		}
    76. 		return true;
    77. 	}
    78. 	bool Find(const K& key)
    79. 	{
    80. 		Node* cur = _root;
    81. 		while (cur)
    82. 		{
    83. 			if (cur->_key > key)
    84. 			{
    85. 				cur = cur->_left;
    86. 			}
    87. 			else if (cur->_key < key)
    88. 			{
    89. 				cur = cur->_right;
    90. 			}
    91. 			else
    92. 			{
    93. 				return true;
    94. 			}
    95. 		}
    96. 		return false;
    97. 	}
    98. 	bool Erase(const K& key)
    99. 	{
    100. 		Node* parent = nullptr;
    101. 		Node* cur = _root;
    102.  
    103. 		while (cur)
    104. 		{
    105. 			if (cur->_key < key)
    106. 			{
    107. 				parent = cur;
    108. 				cur = cur->_right;
    109. 			}
    110. 			else if (cur->_key > key)
    111. 			{
    112. 				parent = cur;
    113. 				cur = cur->_left;
    114. 			}
    115. 			else
    116. 			{
    117. 				if(cur->_left==nullptr)//单个孩子左为空
    118. 				{
    119. 					if (cur == _root)
    120. 					{
    121. 						_root = cur->_right;
    122. 					}
    123. 					else
    124. 					{
    125. 						if (parent->_left == cur)
    126. 						{
    127. 							parent->_left = cur->_right;
    128. 						}
    129. 						else
    130. 						{
    131. 							parent->_right = cur->_right;
    132. 						}
    133. 					}
    134. 					delete cur;
    135. 				}
    136. 				else if(cur->_right==nullptr)//单个孩子右为空
    137. 				{
    138. 					if (cur == _root)
    139. 					{
    140. 						_root = cur->_left;
    141. 						//如果删除根节点，由于根节点没有父节点，因此直接更新根节点
    142. 					}
    143. 					else
    144. 					{
    145. 						if (parent->_left == cur)
    146. 						{
    147. 							parent->_left = cur->_left;
    148. 						}
    149. 						else
    150. 						{
    151. 							parent->_right = cur->_left;
    152. 						}
    153. 					}
    154. 					delete cur;
    155. 				}
    156. 				else//同时有两个孩子
    157. 				{
    158. 					//找要删除节点的右树最小节点或左树最大节点替代
    159. 					Node* minRight = cur->_right;//右树最小
    160. 					Node* pminRight = cur;//minRight的父节点
    161. 					//这里不赋值为nullptr也是考虑到如果删除根节点的空指针问题
    162. 					while (minRight->_left)//最小需要往左找
    163. 					{
    164. 						pminRight = minRight;
    165. 						minRight = minRight->_left;
    166. 					}
    167. 					cur->_key = minRight->_key;//替代
    168. 					//pminRight->_left = minRight->_right;对于根节点会有空指针问题
    169. 					if (pminRight->_left == minRight)//考虑根节点删除问题
    170. 					{
    171. 						pminRight->_left = minRight->_right;
    172. 					}
    173. 					else
    174. 					{
    175. 						pminRight->_right = minRight->_right;
    176. 					}	
    177. 					delete minRight;
    178. 				}
    179. 				return true;
    180. 			}
    181. 		}
    182. 		return false;
    183. 	}
    184.  
    185. 	//递归实现封装接口
    186. 	bool FindR(const K& key)
    187. 	{
    188. 		return _FindR(_root, key);
    189. 	}
    190. 	bool InsertR(const K& key)
    191. 	{
    192. 		return _InsertR(_root, key);
    193. 	}
    194. 	bool EraseR(const K& key)
    195. 	{
    196. 		return _EraseR(_root, key);
    197. 	}
    198. 	void InOrder()//二次封装，方便调用
    199. 	{
    200. 		_InOrder(_root);
    201. 		cout << endl;
    202. 	}
    203.  
    204.  
    205.  
    206. protected://递归实现
    207. 	void Destory(Node*& root)
    208. 	{
    209. 		if (root == nullptr)
    210. 		{
    211. 			return;
    212. 		}
    213. 		Destory(root->_left);
    214. 		Destory(root->_right);
    215. 		delete root;
    216. 		root = nullptr;
    217. 	}
    218. 	Node* Copy(Node*& root)
    219. 	{
    220. 		if (root == nullptr)
    221. 		{
    222. 			return nullptr;
    223. 		}
    224. 		Node* newroot = new Node(root->_key);
    225. 		newroot->_left = Copy(root->_left);
    226. 		newroot->_right = Copy(root->_right);
    227. 		return newroot;
    228. 	}
    229. 	void _InOrder(Node* root)
    230. 	{
    231. 		if (root == nullptr)
    232. 		{
    233. 			return;
    234. 		}
    235. 		_InOrder(root->_left);
    236. 		cout << root->_key << " ";
    237. 		_InOrder(root->_right);
    238. 	}
    239. 	bool _FindR(Node* root, const K& key)
    240. 	{
    241. 		if (root == nullptr)
    242. 		{
    243. 			return false;
    244. 		}
    245. 		if (root->_key = key)
    246. 		{
    247. 			return true;
    248. 		}
    249. 		if (root->_key < key)
    250. 		{
    251. 			return _FindR(root->_right, key);
    252. 		}
    253. 		else
    254. 			return _FindR(root->_left, key);
    255. 	}
    256. 	bool _InsertR(Node*& root, const K& key)
    257. 	//当走到空节点时，root是上一次调用的引用（root->_right或root->_left的引用）
    258. 	{
    259. 		if (root == nullptr)
    260. 		{
    261. 			root = new Node(key);
    262. 			//此时的root节点本就在树中，只不过为空。因此可以直接创建新节点而无需连接
    263. 			return true;
    264. 		}
    265. 		if (root->_key < key)
    266. 		{
    267. 			return _InsertR(root->_right, key);
    268. 		}
    269. 		else if (root->_key > key)
    270. 		{
    271. 			return _InsertR(root->_left, key);
    272. 		}
    273. 		else
    274. 		{
    275. 			return false;
    276. 		}
    277. 	}
    278. 	bool _EraseR(Node*& root, const K& key)
    279. 	{
    280. 		if (root == nullptr)
    281. 		{
    282. 			return false;
    283. 		}
    284.  
    285. 		if (root->_key < key)
    286. 		{
    287. 			return _EraseR(root->_right,key);
    288. 		}
    289. 		else if (root->_key > key)
    290. 		{
    291. 			return _EraseR(root->_left, key);
    292. 		}
    293. 		else
    294. 		{
    295. 			Node* del = root;
    296. 			if (root->_left == nullptr)
    297. 			{
    298. 				root = root->_right;
    299. 			}
    300. 			else if (root->_right == nullptr)
    301. 			{
    302. 				root = root->_left;
    303. 			}
    304. 			else
    305. 			{
    306. 				Node* maxleft = root->_left;
    307. 				while (maxleft->_right)
    308. 				{
    309. 					maxleft = maxleft->_right;
    310. 				}
    311. 				swap(root->_key , maxleft->_key);
    312. 				return _EraseR(_root->_left, key);
    313. 				//转换为子树删除，因为一定是右为空
    314. 				//这里不能是maxleft因为是引用传参
    315. 			}
    316. 			delete del;
    317. 			return true;
    318. 		}
    319. 	}
    320. 	
    321. private:
    322. 	Node* _root = nullptr;
    323. };

    搜索二叉树的应用 

    1.key模型

    K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值

    实际应用：车库比对车牌号，人脸识别

    2.key value模型 

    每一个关键码key，都有与之对应的值Value，即的键值对  

    实际应用：英汉词典中英相互对应、学生姓名与学号相互对应 

    1. #pragma once
    2. //搜索二叉树的key,value模型
    3. #include
    4. using namespace std;
    5. template<class K, class V>
    6. struct BSTreeNode
    7. {
    8. 	BSTreeNode* _left;
    9. 	BSTreeNode* _right;
    10. 	K _key;
    11. 	V _value;
    12.  
    13.  
    14. 	BSTreeNode(const K& key, const V& value)
    15. 		:_left(nullptr)
    16. 		, _right(nullptr)
    17. 		, _key(key)
    18. 		, _value(value)
    19. 	{}
    20. };
    21.  
    22. template<class K, class V>
    23. class BSTree
    24. {
    25. 	typedef BSTreeNode Node;
    26. public:
    27.  
    28. 	bool Insert(const K& key, const V& value)
    29. 	{
    30. 		if (_root == nullptr)
    31. 		{
    32. 			_root = new Node(key, value);
    33. 			return true;
    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. 		cur = new Node(key, value);
    57. 		// 链接
    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. 	Node* Find(const K& key)
    71. 	{
    72. 		Node* cur = _root;
    73. 		while (cur)
    74. 		{
    75. 			if (cur->_key < key)
    76. 			{
    77. 				cur = cur->_right;
    78. 			}
    79. 			else if (cur->_key > key)
    80. 			{
    81. 				cur = cur->_left;
    82. 			}
    83. 			else
    84. 			{
    85. 				return cur;
    86. 			}
    87. 		}
    88.  
    89. 		return nullptr;
    90. 	}
    91.  
    92. 	bool Erase(const K& key)
    93. 	{
    94. 		Node* parent = nullptr;
    95. 		Node* cur = _root;
    96.  
    97. 		while (cur)
    98. 		{
    99. 			if (cur->_key < key)
    100. 			{
    101. 				parent = cur;
    102. 				cur = cur->_right;
    103. 			}
    104. 			else if (cur->_key > key)
    105. 			{
    106. 				parent = cur;
    107. 				cur = cur->_left;
    108. 			}
    109. 			else
    110. 			{
    111. 				// 删除
    112. 				// 1、左为空
    113. 				if (cur->_left == nullptr)
    114. 				{
    115. 					if (cur == _root)
    116. 					{
    117. 						_root = cur->_right;
    118. 					}
    119. 					else
    120. 					{
    121. 						if (parent->_left == cur)
    122. 						{
    123. 							parent->_left = cur->_right;
    124. 						}
    125. 						else
    126. 						{
    127. 							parent->_right = cur->_right;
    128. 						}
    129. 					}
    130.  
    131. 					delete cur;
    132.  
    133. 				} // 2、右为空
    134. 				else if (cur->_right == nullptr)
    135. 				{
    136. 					if (cur == _root)
    137. 					{
    138. 						_root = cur->_left;
    139. 					}
    140. 					else
    141. 					{
    142. 						if (parent->_left == cur)
    143. 						{
    144. 							parent->_left = cur->_left;
    145. 						}
    146. 						else
    147. 						{
    148. 							parent->_right = cur->_left;
    149. 						}
    150. 					}
    151.  
    152. 					delete cur;
    153. 				}
    154. 				else
    155. 				{
    156. 					// 找右树最小节点替代，也可以是左树最大节点替代
    157. 					Node* pminRight = cur;
    158. 					Node* minRight = cur->_right;
    159. 					while (minRight->_left)
    160. 					{
    161. 						pminRight = minRight;
    162. 						minRight = minRight->_left;
    163. 					}
    164.  
    165. 					cur->_key = minRight->_key;
    166.  
    167. 					if (pminRight->_left == minRight)
    168. 					{
    169. 						pminRight->_left = minRight->_right;
    170. 					}
    171. 					else
    172. 					{
    173. 						pminRight->_right = minRight->_right;
    174. 					}
    175.  
    176. 					delete minRight;
    177. 				}
    178.  
    179. 				return true;
    180. 			}
    181. 		}
    182.  
    183. 		return false;
    184. 	}
    185.  
    186.  
    187. 	void InOrder()
    188. 	{
    189. 		_InOrder(_root);
    190. 	}
    191.  
    192. protected:
    193. 	void _InOrder(Node* root)
    194. 	{
    195. 		if (root == nullptr)
    196. 			return;
    197.  
    198. 		_InOrder(root->_left);
    199. 		cout << root->_key << ":" << root->_value<<" ";
    200. 		_InOrder(root->_right);
    201. 	}
    202. private:
    203. 	Node* _root = nullptr;
    204. };

    搜索二叉树性能分析

    插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能

    对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多

    最优情况最坏情况
    树的形态搜索二叉树接近完全二叉树搜索二叉树为单边树
    时间复杂度

    由于搜索二叉树的形态不确定，导致其时间复杂度也取决于二叉树的形态（比如单边树）因此出现了平衡搜索二叉树，与搜索二叉树的不同就在于平衡。始终将二叉树调整到接近完全二叉树，使得时间复杂度为最优解

  • 相关阅读:
    黑客入侵机构，导致2万条信息被卖
    Jupyter Notebook 入门教程
    泛型的介绍和使用方法
    Kotlin--Sealed Class Sealed Interface
    【C++】set和map的底层结构（AVL树&红黑树）
    解决mysql Packet for query is too large
    基于php旅游网站管理系统获取（php毕业设计）
    TS内容学习总结
    Mac SpringBoot项目 Gradle 7.3 转 Maven 手把手教学，包学会~
    Python实现九九乘法表的几种方式，入门必备案例~超级简单~
  • 原文地址：https://blog.csdn.net/RXY24601/article/details/130900444