• 数据结构-二叉搜索树

    目录

    二叉搜索树的概念及结构

    概念

    结构

    二叉搜索树的基本操作

    默认成员函数

    默认构造函数与拷贝构造函数

    赋值重载

    析构函数

    二叉搜索树的插入

    非递归

    递归

    二叉搜索树的遍历

    中序遍历---升序（左根右）

    中序遍历---降序（右根左）

    二叉搜索树的删除

    非递归

    递归

    二叉搜索树的查找

    非递归

    递归

    代码

    二叉搜索树的概念及结构

    概念

       二叉搜索树也称二叉排序树或者二叉查找树，它是在普通二叉树上加入一些特性所形成的：

    • 1，若左子树非空，则左子树上所有结点的值均小于根结点的值。
    • 2，若右子树非空，则右子树上所有结点的值均大于根结点的值。
    • 3，其左右子树也分别是一棵二叉搜索树。

       由二叉搜索树的概念可知，左子树结点值 < 根结点值 < 右子树结点值；所有当二叉搜索树进行中序遍历也就是左根右遍历时，可以得到升序的结果；如果是右根左遍历，就可以得到降序的结果。

    结构

       二叉搜索树的物理结构更适合采用链式结构，_left存储比根结点值小的结点地址，_right存储比根结点值大的结点地址。

    二叉搜索树的基本操作

       对于二叉搜索树的基本操作，我们选择把它的基本操作与其根结点地址封装到一个类中。

    默认成员函数

       二叉搜索树的默认成员函数都需要自己来实现，因为构造与析构涉及到开辟空间与释放空间的操作，而拷贝构造与赋值操作涉及到深拷贝的问题。

    默认构造函数与拷贝构造函数

       默认构造函数只需要实现一个无参的构造函数就可以，其作用就是将_root置空。

    1. // 构造
    2. 	BSTree()
    3. 		:_root(nullptr) 
    4. 	{}

       而拷贝构造函数需要进行深拷贝，就是将被拷贝的二叉搜索树每个结点值拷贝到新开辟结点中，并将新开辟的结点连接成与被拷贝的二叉搜索树结构一样。该拷贝构造过程需要使用到前序遍历的思想，因为先要有双亲结点，才能有左右孩子结点。

    1. // 拷贝构造
    2. 	BSTree(const BSTree& b)
    3. 		:_root(_CopyBSTree(b._root))
    4. 	{
    5.  
    6. 	}

    赋值重载

       赋值重载需要利用到拷贝构造，也就是让被拷贝的二叉搜索树拷贝构造一棵新的二叉搜索树，再让这课新树与需要赋值的树进行交换，即完成赋值。

    1. // 赋值重载
    2. 	BSTree& operator=(BSTree b)
    3. 	{
    4. 		swap(_root, b._root);
    5. 		return *this;
    6. 	}

    析构函数

       析构函数的实现就是通过后序遍历，将二叉搜索树中每一个结点依次释放即可。

    1. // 析构
    2. 	~BSTree()
    3. 	{
    4. 		_DestroyBSTree(_root);
    5. 		_root = nullptr;
    6. 	}

    二叉搜索树的插入

       若原二叉搜索树为空树，则直接将新结点插入到根；否则，根据根结点的值进行判断插入，若插入的值小于根，则插入到左子树中，若插入的值大于根，则插入到右子树中。

       需要注意的是，若插入的值在原二叉搜索树中已经存在了，则插入失败；而且插入的这个新结点一定是叶子结点。

    非递归

    递归

    1. // 插入---递归
    2. 	bool InsertR(const K& key)
    3. 	{
    4. 		return _InsertR(_root, key);
    5. 	}

    二叉搜索树的遍历

       二叉搜索树的中序遍历是最有意义的。

    中序遍历---升序（左根右）

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

    中序遍历---降序（右根左）

    1. void _InOrderReverse(Node* root)
    2. 	{
    3. 		if (root == nullptr)
    4. 		{
    5. 			return;
    6. 		}
    7. 		_InOrderReverse(root->_right);
    8. 		cout << root->_key << " ";
    9. 		_InOrderReverse(root->_left);
    10. 	}
    11.  
    12. // 中序遍历---降序
    13. 	void InOrderReverse()
    14. 	{
    15. 		_InOrderReverse(_root);
    16. 		cout << endl;
    17. 	}

    二叉搜索树的删除

       删除分为三种情况：

    1，若删除的是11,14,17,20这样的叶子结点，可以直接删除，并将其双亲结点指向自己的指针置空。

    2，若删除的是19,20这样有一个孩子的结点，则可以将自己的孩子给其双亲托管，再删除自己。

    3，若删除的是18,13.16这样有两个孩子的结点，可以使用替换删除法：去要删除结点的左右子树中找到可以顶替自己的结点，也就是在其左子树中找最大的结点或者在其右子树中找最小结点。找到之后保存该结点（该结点的特征与1或者2一样）的值，并删除该结点，最后将保存的值给要删除的结点。

    非递归

    递归

    1. // 删除---递归
    2. 	bool EraseR(const K& key)
    3. 	{
    4. 		return _EraseR(_root, key);
    5. 	}

    二叉搜索树的查找

       二叉搜索树的查找就是从根结点开始，沿着某个分支逐层向下比较的过程。先将要查找的值与根结点值比较，如果相等则查找成功；如果不相等，若查找的值小于根结点值，则在根结点的左子树上查找，否则在根结点的右子树上查找；没有找到则返回nullptr。

    非递归

    递归

    1. // 查找---递归
    2. 	Node* FindR(const K& key)
    3. 	{
    4. 		return _FindR(_root, key);
    5. 	}

       二叉搜索树的插入删除查找的时间复杂度为O(n)，因为二叉搜索树不能保证自身的结构不是一棵单支树，所以二叉搜索树需要进行优化成AVL树和红黑树。

    代码

    1. #pragma once
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. template <class K>
    7. struct BSTreeNode
    8. {
    9. 	struct BSTreeNode* _left;
    10. 	struct BSTreeNode* _right;
    11. 	K _key;
    12.  
    13. 	BSTreeNode(const K& key=K())
    14. 		:_left(nullptr)
    15. 		,_right(nullptr)
    16. 		,_key(key)
    17. 	{
    18.  
    19. 	}
    20. };
    21.  
    22. template <class K>
    23. class BSTree
    24. {
    25. 	typedef struct BSTreeNode Node;
    26.  
    27. private:
    28. 	Node* _root;
    29.  
    30. 	void _InOrder(Node* root)
    31. 	{
    32. 		if (root == nullptr)
    33. 		{
    34. 			return;
    35. 		}
    36. 		_InOrder(root->_left);
    37. 		cout << root->_key << " ";
    38. 		_InOrder(root->_right);
    39. 	}
    40.  
    41. 	void _InOrderReverse(Node* root)
    42. 	{
    43. 		if (root == nullptr)
    44. 		{
    45. 			return;
    46. 		}
    47. 		_InOrderReverse(root->_right);
    48. 		cout << root->_key << " ";
    49. 		_InOrderReverse(root->_left);
    50. 	}
    51.  
    52. 	bool _InsertR(Node* &root,const K& key)
    53. 	{
    54. 		if (root == nullptr)
    55. 		{
    56. 			root = new Node(key);
    57. 			return true;
    58. 		}
    59. 		if (root->_key < key)
    60. 		{
    61. 			return _InsertR(root->_right, key);
    62. 		}
    63. 		else if(root->_key>key)
    64. 		{
    65. 			return _InsertR(root->_left, key);
    66. 		}
    67. 		else
    68. 		{
    69. 			return false;
    70. 		}
    71. 	}
    72.  
    73. 	Node* _FindR(Node* root, const K& key)
    74. 	{
    75. 		if (root == nullptr) // 查找失败
    76. 		{
    77. 			return nullptr;
    78. 		}
    79.  
    80. 		if (root->_key < key) // 大于根结点值，往根结点的右子树上查找
    81. 		{
    82. 			return _FindR(root->_right, key);
    83. 		}
    84. 		else if(root->_key>key) // 小于根结点值，往根结点的左子树上查找
    85. 		{
    86. 			return _FindR(root->_left, key);
    87. 		}
    88. 		else // 查找成功
    89. 		{
    90. 			return root; // 查找成功
    91. 		}
    92. 	}
    93.  
    94. 	bool _EraseR(Node*& root, const K& key)
    95. 	{
    96. 		if (root == nullptr)
    97. 		{
    98. 			return false;
    99. 		}
    100. 		if (root->_key < key)
    101. 		{
    102. 			return _EraseR(root->_right, key);
    103. 		}
    104. 		else if (root->_key > key)
    105. 		{
    106. 			return _EraseR(root->_left, key);
    107. 		}
    108. 		else // 找到了要删除的结点
    109. 		{
    110. 			if (root->_left == nullptr)
    111. 			{
    112. 				Node* del = root;
    113. 				root = root->_right;
    114. 				delete del;
    115. 				return true;
    116. 			}
    117. 			else if(root->_right==nullptr)
    118. 			{
    119. 				Node* del = root;
    120. 				root = root->_left;
    121. 				delete del;
    122. 				return true;
    123. 			}
    124. 			else
    125. 			{
    126. 				Node* min = root->_right;
    127. 				while (min->_left)
    128. 				{
    129. 					min = min->_left;
    130. 				}
    131. 				K tmp = min->_key;
    132.  
    133. 				_EraseR(root, tmp);
    134.  
    135. 				root->_key = tmp;
    136. 				return true;
    137. 			}
    138. 		}
    139. 	}
    140.  
    141. 	Node* _CopyBSTree(Node* root)
    142. 	{
    143. 		if (root == nullptr)
    144. 		{
    145. 			return nullptr;
    146. 		}
    147.  
    148. 		Node* newNode = new Node(root->_key);
    149.  
    150. 		newNode->_left = _CopyBSTree(root->_left);
    151. 		newNode->_right = _CopyBSTree(root->_right);
    152.  
    153. 		return newNode;
    154. 	}
    155.  
    156. 	void _DestroyBSTree(Node* root)
    157. 	{
    158. 		if (root == nullptr)
    159. 		{
    160. 			return;
    161. 		}
    162. 		_DestroyBSTree(root->_left);
    163. 		_DestroyBSTree(root->_right);
    164. 		delete root;
    165. 	}
    166.  
    167.  
    168. public: 
    169. 	// 构造
    170. 	BSTree()
    171. 		:_root(nullptr) 
    172. 	{}
    173.  
    174. 	// 拷贝构造
    175. 	BSTree(const BSTree& b)
    176. 		:_root(_CopyBSTree(b._root))
    177. 	{
    178.  
    179. 	}
    180.  
    181. 	// 赋值重载
    182. 	BSTree& operator=(BSTree b)
    183. 	{
    184. 		swap(_root, b._root);
    185. 		return *this;
    186. 	}
    187.  
    188. 	// 析构
    189. 	~BSTree()
    190. 	{
    191. 		_DestroyBSTree(_root);
    192. 		_root = nullptr;
    193. 	}
    194.  
    195. 	// 插入
    196. 	bool Insert(const K& key) //二叉搜索树的插入与单链表的尾插相似，分两种情况
    197. 	{
    198. 		if (_root == nullptr) // 当二叉搜索树为空树时，直接将插入的结点当成根结点
    199. 		{
    200. 			_root = new Node(key);
    201. 			return true;
    202. 		}
    203.  
    204. 		Node* prev = nullptr;
    205. 		Node* curr = _root;
    206.  
    207. 		while (curr) // 当二叉搜索树不为空树时，需要寻找满足二叉搜索树特性的位置，并找到满足位置的双亲结点的位置
    208. 		{
    209. 			if (curr->_key < key) // 当key大于双亲结点的_key往右走
    210. 			{
    211. 				prev = curr;
    212. 				curr = curr->_right;
    213. 			}
    214. 			else if(curr->_key>key) // 当key小于双亲结点的_key往左走
    215. 			{
    216. 				prev = curr;
    217. 				curr = curr->_left;
    218. 			}
    219. 			else // 如果相等插入失败
    220. 			{
    221. 				return false;
    222. 			}
    223. 		}
    224.  
    225. 		if (prev->_key < key) // prev为插入位置的双亲结点位置，保证插入的结点成功链接到二叉搜索树中
    226. 		{
    227. 			prev->_right = new Node(key);
    228. 		}
    229. 		else
    230. 		{
    231. 			prev->_left = new Node(key);
    232. 		}
    233.  
    234. 		return true;
    235. 	}
    236.  
    237. 	// 中序遍历---升序
    238. 	void InOrder()
    239. 	{
    240. 		_InOrder(_root);
    241. 		cout << endl;
    242. 	}
    243. 	
    244. 	// 中序遍历---降序
    245. 	void InOrderReverse()
    246. 	{
    247. 		_InOrderReverse(_root);
    248. 		cout << endl;
    249. 	}
    250.  
    251. 	// 查找
    252. 	Node* Find(const K& key) // 二叉搜索树的查找与单链表的查找相似
    253. 	{
    254. 		Node* curr = _root;
    255. 		while (curr)
    256. 		{
    257. 			if (curr->_key < key)
    258. 			{
    259. 				curr = curr->_right;
    260. 			}
    261. 			else if (curr->_key > key)
    262. 			{
    263. 				curr = curr->_left;
    264. 			}
    265. 			else
    266. 			{
    267. 				return curr;
    268. 			}
    269. 		}
    270. 		return nullptr; // return curr; 也行
    271. 	}
    272.  
    273. 	// 删除
    274. 	bool Erase(const K&key)
    275. 	{
    276. 		Node* prev = nullptr;
    277. 		Node* curr = _root;
    278. 		while (curr) // 寻找值为key的结点，prev为该结点的双亲结点
    279. 		{
    280. 			if (curr->_key < key) // 如果key大于当前结点的_key，则往右走
    281. 			{
    282. 				prev = curr;
    283. 				curr = curr->_right;
    284. 			}
    285. 			else if(curr->_key>key) // 如果key小于当前结点的_key，则往左走
    286. 			{
    287. 				prev = curr;
    288. 				curr = curr->_left;
    289. 			}
    290. 			else // 找到_key为key的结点---该结点分为三类：1，没有左右孩子结点 2，有一个孩子结点 3，左右孩子结点都
    291. 			{
    292. 				if (curr->_left == nullptr) // 如果该结点没有左孩子结点，则需要将该结点的右结点给其双亲结点
    293. 				{
    294. 					if (curr == _root) // 如果删除的是根结点，则将_root改为其右子树
    295. 					{
    296. 						_root = curr->_right;
    297. 					}
    298. 					else 
    299. 					{
    300. 						if (prev->_left == curr) // 判断删除的结点是双亲的左孩子还是右孩子
    301. 						{
    302. 							prev->_left = curr->_right;
    303. 						}
    304. 						else
    305. 						{
    306. 							prev->_right = curr->_right;
    307. 						}
    308. 					}
    309. 					delete curr;
    310. 					return true;
    311. 				}
    312. 				else if (curr->_right == nullptr) // 如果该结点没有右孩子结点，则需要将该结点的左结点给其双亲结点
    313. 				{
    314. 					if (curr == _root) // 如果删除的是根结点，则将_root改为其左子树
    315. 					{
    316. 						_root = curr->_left;
    317. 					}
    318. 					else
    319. 					{
    320. 						if (prev->_left == curr)// 判断删除的结点是双亲的左孩子还是右孩子
    321. 						{
    322. 							prev->_left = curr->_left;
    323. 						}
    324. 						else
    325. 						{
    326. 							prev->_right = curr->_left;
    327. 						}
    328. 					}
    329. 					delete curr;
    330. 					return true;
    331. 				}
    332. 				else // 如果删除的结点左右孩子都有，则进行替换删除
    333. 				{
    334. 					
    335. 					/*Node* minPrev = curr; 
    336. 					Node* min = curr->_right; // 寻找删除结点的右子树中最小结点
    337. 					while (min->_left)
    338. 					{
    339. 						minPrev = min;
    340. 						min = min->_left;
    341. 					}
    343. 					if (minPrev == curr) // 避免最小结点是删除结点的右孩子结点
    344. 					{
    345. 						minPrev->_right = min->_right;
    346. 					}
    347. 					else
    348. 					{
    349. 						minPrev->_left = min->_right;
    350. 					}
    352. 					curr->_key = min->_key;
    353. 					delete min;*/
    354.  
    355. 					Node* min = curr->_right; // 选出右子树最小的结点
    356. 					while (min->_left)
    357. 					{
    358. 						min = min->_left;
    359. 					}
    360. 					K tmp = min->_key; // 保存右子树最小结点的值
    361. 					Erase(tmp); // 将tmp值的结点删除
    362. 					_root->_key = tmp; // 再将tmp的值赋给有两个孩子的结点，想当将这个结点删除
    363. 					return true;
    364. 				}
    365. 			}
    366. 		}
    367. 		return false; // 没有找到删除的结点，则说明删除失败，返回false
    368. 	}
    369.  
    370. 	// 插入---递归
    371. 	bool InsertR(const K& key)
    372. 	{
    373. 		return _InsertR(_root, key);
    374. 	}
    375.  
    376. 	// 查找---递归
    377. 	Node* FindR(const K& key)
    378. 	{
    379. 		return _FindR(_root, key);
    380. 	}
    381.  
    382. 	// 删除---递归
    383. 	bool EraseR(const K& key)
    384. 	{
    385. 		return _EraseR(_root, key);
    386. 	}
    387.  
    388. };
  • 相关阅读:
    高性能AC算法多关键词匹配文本功能Java实现
    STC 51单片机43——看门狗
    关于WebMvcConfigurer
    SpringBoot整合Kafka (一)
    聚合支付的特点与应用建议
    slf4j简介说明
    霍尔电流传感器如何进行可靠性测试？主要应用在哪些领域？
    git使用整理
    被疫情占据的上半年，你还好么？| 2022年中总结
    Nodejs安装和下载
  • 原文地址：https://blog.csdn.net/m0_61433144/article/details/126208652