• ＜C++＞手撕搜索二叉树

    目录

    一、搜索二叉树的性质

    二、搜索二叉树的结构定义

    三、手撕搜索二叉树非递归

    1）Insert()

    2）Find()

    3）Erase()

    4）InOder()

    5）BSTree(const BSTree& t) 拷贝构造

    6）~BSTree()析构函数

    四、手撕搜索二叉树递归

    1）InsertR()

    2）FindR()

    3）EraseR()

    五、搜索二叉树完整代码

    一、搜索二叉树的性质

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

    二、搜索二叉树的结构定义

    搜索二叉树主要实现的是K或K/Value模型，这里我们使用K模型来定义，即可以用O(N)的时间复杂度来进行K值的搜索。

     

    使用模板来定义

    1. template<class K>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode<K>* _left;
    5. 	BSTreeNode<K>* _right;
    6. 	K _key;
    7.  
    8. 	BSTreeNode(const K& key)
    9. 		:_left(nullptr)
    10. 		,_right(nullptr)
    11. 		,_key(key)
    12. 	{
    13.  
    14. 	}
    15. };

    三、手撕搜索二叉树非递归

    1）Insert()

    插入有两种情况：

    • _root == nullptr 根节点等于空

    直接new a Node插入即可

    1. if (_root == nullptr)
    2. {
    3. 	_root = new Node(key);
    4. 	return true;
    5. }
    • _root != nullptr 根节点不等于空

    我们需要找到适合key值的空节点位置，通过搜索二叉树的性质进行排查位置

    1. 			Node* parent = nullptr;
    2. 			Node* cur = _root;
    3. 			while (cur)
    4. 			{
    5. 				if (cur->_key < key)
    6. 				{
    7. 					parent = cur;
    8. 					cur = cur->_right;
    9. 				}
    10. 				else if (cur->_key > key)
    11. 				{
    12. 					parent = cur;
    13. 					cur = cur->_left;
    14. 				}
    15. 				else
    16. 				{
    17. 					return false;
    18. 				}
    19. 			}
    20.  
    21. 			//开始插入
    22. 			cur = new Node(key);
    23. 			if (parent->_key < key)
    24. 			{
    25. 				parent->_right = cur;
    26. 			}
    27. 			else
    28. 			{
    29. 				parent->_left = cur;
    30. 			}

     

     

     

    2）Find()

    直接通过搜索二叉树的性质就可以进行查找，当key值大于cur->_key的值时，就查找cur的右子树，key值小于cur->_key的值时，就查找cur的左子树，直到找到，或者找不到cur == nullptr结束，即逻辑和Inser中的逻辑大同小异；

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

    3）Erase()

    删除分三种情况：

    • 删除节点没有孩子
    • 删除节点有一个孩子
    1. 有一个左孩子
    2. 有一个右孩子
    • 删除节点有两个孩子

    前面两种代码可以合并处理

    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. 				//开始删除
    20. 				if (cur->_left == nullptr)
    21. 				{
    22. 					if (cur == _root)
    23. 					{
    24. 						_root = cur->_right;
    25. 					}
    26. 					else
    27. 					{
    28. 						if (cur == parent->_left)
    29. 						{
    30. 							parent->_left = cur->_right;
    31. 						}
    32. 						else
    33. 						{
    34. 							parent->_right = cur->_right;
    35. 						}
    36. 					}
    37.  
    38. 					delete cur;
    39. 					cur = nullptr;
    40. 				}
    41. 				else if (cur->_right == nullptr)
    42. 				{
    43. 					if (cur == _root)
    44. 					{
    45. 						_root = cur->_left;
    46. 					}
    47. 					else
    48. 					{
    49. 						if (cur == parent->_left)
    50. 						{
    51. 							parent->_left = cur->_left;
    52. 						}
    53. 						else
    54. 						{
    55. 							parent->_right = cur->_left;
    56. 						}
    57. 					}
    58.  
    59. 					delete cur;
    60. 					cur = nullptr;
    61. 				}
    62. 				else
    63. 				{
    64. 					Node* minParent = cur;
    65. 					Node* min = cur->_right;
    66. 					while (min->_left)
    67. 					{
    68. 						minParent = min;
    69. 						min = min->_left;
    70. 					}
    71.  
    72. 					swap(cur->_key, min->_key);
    73.  
    74. 					if (minParent->_left == min)
    75. 					{
    76. 						minParent->_left = min->_right;
    77. 					}
    78. 					else
    79. 					{
    80. 						minParent->_right = min->_right;
    81. 					}
    82.  
    83. 					delete min;
    84. 					min = nullptr;
    85. 				}
    86.  
    87. 				return true;
    88. 			}
    89. 		}
    90.  
    91. 		return false;
    92. 	}

    4）InOder()

    使用二叉树的中序遍历--midorder traverse

    特点：

    中序遍历后的值排列是有序的

    1.     void InOrder()
    2.     {
    3. 		_InOrder(_root);
    4. 		return;
    5.     }
    6.  
    7. 	void _InOrder(Node* root)
    8. 	{
    9. 		if (root == nullptr)
    10. 		{
    11. 			return;
    12. 		}
    13.  
    14. 		_InOrder(root->_left);
    15. 		cout << root->_key << " ";
    16. 		_InOrder(root->_right);
    17. 	}

    5）BSTree(const BSTree& t) 拷贝构造

    使用前序遍历构造

    1.  
    2. 	BSTree(const BSTree<K>& t)
    3. 	{
    4. 		_Copy(t._root);
    5. 	}
    6.  
    7.     Node* _Copy(Node* root) // 使用前序遍历构造
    8. 	{
    9. 		if (root == nullptr)
    10. 		{
    11. 			return;
    12. 		}
    13.  
    14. 		Node* copyRoot = new Node(root->_key);
    15. 		copyRoot->_left = _Copy(root->_left);
    16. 		copyRoot->_left = _Copy(root->_right);
    17. 		return copyRoot;
    18. 	}

    6）~BSTree()析构函数

    使用后序销毁

    1. 	~BSTree()
    2. 	{
    3. 		_Destory(_root);
    4. 	}
    5.  
    6.     void _Destory(Node* root) // 使用后序销毁
    7. 	{
    8. 		if (root == nullptr)
    9. 		{
    10. 			return;
    11. 		}
    12.  
    13. 		_Destory(root->_left);
    14. 		_Destory(root->_right);
    15. 		delete root;
    16. 		root = nullptr;
    17. 	}

    四、手撕搜索二叉树递归

    1）InsertR()

    1. 	bool InertR(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);
    11. 			return true;
    12. 		}
    13.  
    14. 		if (root->_key < key)
    15. 		{
    16. 			return _InsertR(root->_right, key);
    17. 		}
    18. 		else if (root->_key > key)
    19. 		{
    20. 			return _InsertR(root->_left, key);
    21. 		}
    22. 		else
    23. 		{
    24. 			return false;
    25. 		}
    26. 	}

    2）FindR()

    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 (root->_key < key)
    14. 		{
    15. 			return _FindR(root->_right);
    16. 		}
    17. 		else if (root->_key > key)
    18. 		{
    19. 			return _FindR(root->_left);
    20. 		}
    21. 		else
    22. 		{
    23. 			return true;
    24. 		}
    25. 	}

    3）EraseR()

    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 (root->_key < key)
    14. 		{
    15. 			return _EraseR(root->_right, key);
    16. 		}
    17. 		else if (root->_key > key)
    18. 		{
    19. 			return _EraseR(root->_left, key);
    20. 		}
    21. 		else
    22. 		{
    23. 			Node* del = root;
    24. 			if (root->_left == nullptr)
    25. 			{
    26. 				root = root->_right;
    27. 			}
    28. 			else if (root->_right == nullptr)
    29. 			{
    30. 				root = root->_left;
    31. 			}
    32. 			else
    33. 			{
    34. 				//找右数的最左节点
    35. 				Node* min = root->_right;
    36. 				while (min->_left)
    37. 				{
    38. 					min = min->_left;
    39. 				}
    40.  
    41. 				swap(root->_key, min->_key);
    42. 				return _InserR(root->_right, key);
    43. 			}
    44.  
    45. 			delete del;
    46. 			return true;
    47. 		}
    48. 	}

    五、搜索二叉树完整代码

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

  • 相关阅读:
    Vue Slot插槽：组件化的艺术
    死锁的成因和对应的解决方案
    大家一起来学习如何使用spring.factories
    你需要的导航网站，这里都有
    TS编译器选项——指定编译ES版本和模块化使用规范
    计算机学院院长第一课——前辈的经验
    Labelme安装以及使用教程
    前端面试真题
    图片链接打不开检测工具-免费链接失败检测软件
    C++算法：分发糖果
  • 原文地址：https://blog.csdn.net/weixin_63246064/article/details/128122126