• C++ 之二叉搜索树

    目录

    学习目标：

    1.二叉搜索树

    1.1二叉搜索树的概念

     1.2二叉搜索树的操作

    1.二叉搜索树的查找

    2.二叉树的插入

    3.二叉树的删除*

    2.二叉搜索树的实现

    3.二叉树性能分析

    1.二叉搜索树

    1.1二叉搜索树的概念

    二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

    若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

    若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

    它的左右子树也分别为二叉搜索树

     1.2二叉搜索树的操作

    1.二叉搜索树的查找

    我们根据二叉树的性质可以知道，每棵树的左子树上的节点的值都小于根，右子树上的节点的值都大于根所以我们可以这样查找

    a.从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

    b、最多查找高度次，走到到空，还没找到，这个值不存在

    2.二叉树的插入

    a. 树为空，则直接新增节点，赋值给root指针

    b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

     

    3.二叉树的删除*

    二叉树的删除分为四种情况：

    1.要删除的节点 为叶子节点，这一种我们直接删除，没有任何影响

    2.要删除的节点 的左子树为空，这个时候我们需要记录一下要删除节点的父节点，让他的父节点来继承它的子树

    3.要删除的节点 的右子树为空，这个时候我们需要记录一下要删除节点的父节点，让他的父节点来继承它的子树

    4.要删除的节点 左右子树都不为空，这种情况最为麻烦，我们可以使用替换删除法

    找到要删除节点的右子树的最左节点或者 左子树的左右节点，替换删除的节点，并记录cur的父节点。

    代码如下：

    1. 	bool Erase(const K& key)
    2. 		{
    3. 			Node* parent = nullptr;
    4. 			Node* cur = _root;
    5. 			while (cur)
    6. 			{
    7. 				if (cur->_key < key)
    8. 				{
    9. 					parent = cur;
    10. 					cur = cur->_right;
    11. 				}
    12. 				else if (cur->_key > key)
    13. 				{
    14. 					parent = cur;
    15. 					cur = cur->_left;
    16. 				}
    17. 				else
    18. 				{
    19. 					if (cur->_left == nullptr)//左子树为空
    20. 					{
    21. 						if (cur == _root)
    22. 						{
    23. 							_root = cur->_right;
    24. 						}
    25. 						else
    26. 						{
    27. 							if (cur == parent->_right)
    28. 							{
    29. 								parent->_right = cur->_right;
    30. 							}
    31. 							else
    32. 							{
    33. 								parent->_left = cur->_right;
    34. 							}
    35. 						}
    36.  
    37. 						delete cur;
    38. 						return true;
    39. 					}
    40. 					else if (cur->_right == nullptr)//右子树为空
    41. 					{
    42. 						if (cur == _root)
    43. 						{
    44. 							_root = cur->_left;
    45. 						}
    46. 						else
    47. 						{
    48. 							if (cur == parent->_right)
    49. 							{
    50. 								parent->_right = cur->_left;
    51. 							}
    52. 							else
    53. 							{
    54. 								parent->_left = cur->_left;
    55. 							}
    56. 						}
    57.  
    58. 						delete cur;
    59. 						return true;
    60. 					}
    61. 					else //左右子树都为空的情况  用右子树的最左节点替代
    62. 					{
    63. 						// 替换法
    64. 						Node* rightMinParent = cur;//不初始化为空是为了防止删除根结点
    65. 						Node* rightMin = cur->_right;
    66. 						while (rightMin->_left)
    67. 						{
    68. 							rightMinParent = rightMin;
    69. 							rightMin = rightMin->_left;
    70. 						}
    71.  
    72. 						cur->_key = rightMin->_key;
    73.  
    74. 						if (rightMin == rightMinParent->_left)//被替换的节点的父节点来继承左右子树
    75. 							rightMinParent->_left = rightMin->_right;
    76. 						else
    77. 							rightMinParent->_right = rightMin->_right;
    78.  
    79. 						delete rightMin;
    80. 						return true;
    81. 					}
    82. 				}
    83. 			}
    84.  
    85. 			return false;
    86. 		}

    2.二叉搜索树的实现

    1. #pragma once
    2. namespace key
    3. {
    4. 	template<class K>
    5. 	struct BSTreeNode
    6. 	{
    7. 		typedef BSTreeNode Node;
    8.  
    9. 		Node* _left;
    10. 		Node* _right;
    11. 		K _key;
    12.  
    13. 		BSTreeNode(const K& key)
    14. 			:_left(nullptr)
    15. 			, _right(nullptr)
    16. 			, _key(key)
    17. 		{}
    18. 	};
    19.  
    20. 	template<class K>
    21. 	class BSTree
    22. 	{
    23. 		typedef BSTreeNode Node;
    24. 	public:
    25. 		BSTree() = default;
    26.  
    27. 		BSTree(const BSTree& t)
    28. 		{
    29. 			_root = Copy(t._root);
    30. 		}
    31.  
    32. 		BSTree& operator=(BSTree t)
    33. 		{
    34. 			swap(_root, t._root);
    35. 			return *this;
    36. 		}
    37.  
    38. 		~BSTree()
    39. 		{
    40. 			Destroy(_root);
    41. 		}
    42.  
    43. 		bool Insert(const K& key)
    44. 		{
    45. 			if (_root == nullptr)
    46. 			{
    47. 				_root = new Node(key);
    48. 				return true;
    49. 			}
    50.  
    51. 			Node* parent = nullptr;
    52. 			Node* cur = _root;
    53. 			while (cur)
    54. 			{
    55. 				if (cur->_key < key)
    56. 				{
    57. 					parent = cur;
    58. 					cur = cur->_right;
    59. 				}
    60. 				else if (cur->_key > key)
    61. 				{
    62. 					parent = cur;
    63. 					cur = cur->_left;
    64. 				}
    65. 				else
    66. 				{
    67. 					return false;
    68. 				}
    69. 			}
    70.  
    71. 			cur = new Node(key);
    72. 			if (parent->_key < key)
    73. 			{
    74. 				parent->_right = cur;
    75. 			}
    76. 			else
    77. 			{
    78. 				parent->_left = cur;
    79. 			}
    80.  
    81. 			return true;
    82. 		}
    83.  
    84. 		bool Find(const K& key)
    85. 		{
    86. 			Node* cur = _root;
    87. 			while (cur)
    88. 			{
    89. 				if (cur->_key < key)
    90. 				{
    91. 					cur = cur->_right;
    92. 				}
    93. 				else if (cur->_key > key)
    94. 				{
    95. 					cur = cur->_left;
    96. 				}
    97. 				else
    98. 				{
    99. 					return true;
    100. 				}
    101. 			}
    102.  
    103. 			return false;
    104. 		}
    105.  
    106. 		bool Erase(const K& key)
    107. 		{
    108. 			Node* parent = nullptr;
    109. 			Node* cur = _root;
    110. 			while (cur)
    111. 			{
    112. 				if (cur->_key < key)
    113. 				{
    114. 					parent = cur;
    115. 					cur = cur->_right;
    116. 				}
    117. 				else if (cur->_key > key)
    118. 				{
    119. 					parent = cur;
    120. 					cur = cur->_left;
    121. 				}
    122. 				else
    123. 				{
    124. 					if (cur->_left == nullptr)//左子树为空
    125. 					{
    126. 						if (cur == _root)
    127. 						{
    128. 							_root = cur->_right;
    129. 						}
    130. 						else
    131. 						{
    132. 							if (cur == parent->_right)
    133. 							{
    134. 								parent->_right = cur->_right;
    135. 							}
    136. 							else
    137. 							{
    138. 								parent->_left = cur->_right;
    139. 							}
    140. 						}
    141.  
    142. 						delete cur;
    143. 						return true;
    144. 					}
    145. 					else if (cur->_right == nullptr)//右子树为空
    146. 					{
    147. 						if (cur == _root)
    148. 						{
    149. 							_root = cur->_left;
    150. 						}
    151. 						else
    152. 						{
    153. 							if (cur == parent->_right)
    154. 							{
    155. 								parent->_right = cur->_left;
    156. 							}
    157. 							else
    158. 							{
    159. 								parent->_left = cur->_left;
    160. 							}
    161. 						}
    162.  
    163. 						delete cur;
    164. 						return true;
    165. 					}
    166. 					else //左右子树都为空的情况  用右子树的最左节点替代
    167. 					{
    168. 						// 替换法
    169. 						Node* rightMinParent = cur;//不初始化为空是为了防止删除根结点
    170. 						Node* rightMin = cur->_right;
    171. 						while (rightMin->_left)
    172. 						{
    173. 							rightMinParent = rightMin;
    174. 							rightMin = rightMin->_left;
    175. 						}
    176.  
    177. 						cur->_key = rightMin->_key;
    178.  
    179. 						if (rightMin == rightMinParent->_left)//被替换的节点的父节点来继承左右子树
    180. 							rightMinParent->_left = rightMin->_right;
    181. 						else
    182. 							rightMinParent->_right = rightMin->_right;
    183.  
    184. 						delete rightMin;
    185. 						return true;
    186. 					}
    187. 				}
    188. 			}
    189.  
    190. 			return false;
    191. 		}
    192.  
    193. 		void InOrder()
    194. 		{
    195. 			_InOrder(_root);
    196. 			cout << endl;
    197. 		}
    198. 		bool FindR(const K& key)
    199. 		{
    200. 			return _FindR(_root, key);
    201. 		}
    202.  
    203. 		bool InsertR(const K& key)
    204. 		{
    205. 			return _InsertR(_root, key);
    206. 		}
    207.  
    208. 		bool EraseR(const K& key)
    209. 		{
    210. 			return _EraseR(_root, key);
    211. 		}
    212. 	private:
    213. 		void Destroy(Node* root)
    214. 		{
    215. 			if (root == nullptr)
    216. 				return;
    217.  
    218. 			Destroy(root->_left);
    219. 			Destroy(root->_right);
    220. 			delete root;
    221. 		}
    222.  
    223. 		Node* Copy(Node* root)
    224. 		{
    225. 			if (root == nullptr)
    226. 				return nullptr;
    227.  
    228. 			Node* newRoot = new Node(root->_key);
    229. 			newRoot->_left = Copy(root->_left);
    230. 			newRoot->_right = Copy(root->_right);
    231. 			return newRoot;
    232. 		}
    233.  
    234.  
    235. 		bool _EraseR(Node*& root, const K& key)
    236. 		{
    237. 			if (root == nullptr)
    238. 				return false;
    239.  
    240. 			if (root->_key < key)
    241. 			{
    242. 				return _EraseR(root->_right, key);
    243. 			}
    244. 			else if (root->_key > key)
    245. 			{
    246. 				return _EraseR(root->_left, key);
    247. 			}
    248. 			else
    249. 			{
    250. 				Node* del = root;
    251. 				if (root->_right == nullptr)
    252. 				{
    253. 					root = root->_left;
    254. 				}
    255. 				else if (root->_left == nullptr)
    256. 				{
    257. 					root = root->_right;
    258. 				}
    259. 				else
    260. 				{
    261. 					Node* rightMin = root->_right;
    262. 					while (rightMin->_left)
    263. 					{
    264. 						rightMin = rightMin->_left;
    265. 					}
    266.  
    267. 					swap(root->_key, rightMin->_key);
    268.  
    269. 					return _EraseR(root->_right, key);
    270. 				}
    271.  
    272. 				delete del;
    273. 				return true;
    274. 			}
    275. 		}
    276.  
    277. 		bool _InsertR(Node*& root, const K& key)
    278. 		{
    279. 			if (root == nullptr)
    280. 			{
    281. 				root = new Node(key);
    282. 				return true;
    283. 			}
    284.  
    285. 			if (root->_key < key)
    286. 			{
    287. 				return _InsertR(root->_right, key);
    288. 			}
    289. 			else if (root->_key > key)
    290. 			{
    291. 				return _InsertR(root->_left, key);
    292. 			}
    293. 			else
    294. 			{
    295. 				return false;
    296. 			}
    297. 		}
    298.  
    299. 		bool _FindR(Node* root, const K& key)
    300. 		{
    301. 			if (root == nullptr)
    302. 				return false;
    303.  
    304. 			if (root->_key < key)
    305. 			{
    306. 				return _FindR(root->_right, key);
    307. 			}
    308. 			else if (root->_key > key)
    309. 			{
    310. 				return _FindR(root->_left, key);
    311. 			}
    312. 			else
    313. 			{
    314. 				return true;
    315. 			}
    316. 		}
    317.  
    318. 		void _InOrder(Node* root)
    319. 		{
    320. 			if (root == nullptr)
    321. 				return;
    322.  
    323. 			_InOrder(root->_left);
    324. 			cout << root->_key << " ";
    325. 			_InOrder(root->_right);
    326. 		}
    327.  
    328. 	private:
    329. 		Node* _root = nullptr;
    330. 	};
    331. }

    3.二叉树性能分析

    插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能
    对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

    但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

     

    如果二叉树成为了单支树，搜索和查找效率就会变得非常差。

  • 相关阅读:
    甬矽电子在科创板上市：市值达到122亿元，王顺波为实际控制人
    linux查看端口是否开放
    如何修复 HTML 中的乱码
    Java8 Stream流式操作接口详解
    作图从此不求人，代谢组学宝藏作图能力提升班你来不来？
    DVWA通关攻略零到一【全】
    OpenGL纹理转换谜团：纹理写入FRAMEBUFFER后的镜像现象
    贝锐蒲公英异地组网方案，如何阻断网络安全威胁？
    【数据结构与算法】- 图（算法）
    cuda和cuDNN的安装
  • 原文地址：https://blog.csdn.net/qq_74732628/article/details/138163984