• 数据结构与算法_二叉搜索树

    二叉搜索树可以说是二叉树的升级版，在数据的查找上，它优于普通二叉树。要让普通二叉树成为二叉搜索树，就要对于树中每个节点X，它左子树中所有节点元素的值小于X中的值，它右子树中所有节点元素的值大于X中的值。

    请看下边这两棵树，左边的树是一棵二叉搜索树，右边的树并不是二叉搜索树，因为7比6要大，而它却在6的左子树中。

    目录

    一、二叉搜索树的概念

    二、二叉搜索树操作

    查找

    插入

    删除

    三、二叉搜索树的代码实现

    四、二叉搜索树的应用

    key模型

    KV模型

    key模型和KV模型的实现：

    一、二叉搜索树的概念

    二叉搜索树又称二叉排序树，它可以是一棵空树......也可以是具有如下性质的二叉树：

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

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

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

    二、二叉搜索树操作

    查找

    a、从根节点开始比较，查找，比根大则往右边走查找，比根小则往左边走查找；

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

    为什么说最多查找高度次？因为，如果二叉搜索树是下面这种形态，其实就趋近于链表了：

    插入

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

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

    如下图，是依次插入16和0后的二叉搜索树：

    删除

    首先查找元素是否存在于二叉搜索树中。如果不存咋，就返回。如果存在，应该根据下面四种情况来删除：

    a.要删除的节点无孩子节点；

    b.要删除的节点只有左孩子节点；

    c.要删除的节点只有右孩子节点；

    d.要删除的节点有左、右孩子节点。

    看起来，有四种情况，事实上，a和b的情况可以放在一起考虑，那么删除过程如下：

    情况b：删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点——直接删除

    情况c：删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点——直接删除

    情况d：在它的右子树中寻找中序下的第一个节点（关键码最小），用它的值填补到被删除节点中，再来处理该节点的删除问题——替换法删除

    如下图，依次删除7、14、3、8

    7和14属于直接删除的场景

    3和8属于需要替换法进行删除的场景

    三、二叉搜索树的代码实现

    1. template<class K>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode* _left;
    5. 	BSTreeNode* _right;
    6. 	K _key;
    7.  
    8. 	BSTreeNode(const K& key)
    9. 		:_left(nullptr)
    10. 		, _right(nullptr)
    11. 		, _key(key)
    12. 	{}
    13. };
    14.  
    15. template<class K>
    16. class BSTree
    17. {
    18. 	typedef struct BSTreeNode Node;
    19. public:
    20. 	BSTree()
    21. 		:_root(nullptr)
    22. 	{}
    23.  
    24. 	bool Insert(const K& key)
    25. 	{
    26. 		if (_root == nullptr)
    27. 		{
    28. 			_root = new Node(key);
    29. 			return true;
    30. 		}
    31.  
    32. 		Node* parent = nullptr;
    33. 		Node* cur = _root;
    34. 		while (cur)
    35. 		{
    36. 			if (cur->_key < key)
    37. 			{
    38. 				parent = cur;
    39. 				cur = cur->_right;
    40. 			}
    41. 			else if (cur->_key > key)
    42. 			{
    43. 				parent = cur;
    44. 				cur = cur->_left;
    45. 			}
    46. 			else
    47. 			{
    48. 				return false;
    49. 			}
    50. 		}
    51. 		cur = new Node(key);
    52. 		if (parent->_key < key)
    53. 		{
    54. 			parent->_right = cur;
    55. 		}
    56. 		else
    57. 		{
    58. 			parent->_left = cur;
    59. 		}
    60. 		return true;
    61. 	}
    62.  
    63. 	bool Find(const K& key)
    64. 	{
    65. 		Node* cur = _root;
    66. 		while (cur)
    67. 		{
    68. 			if (cur->_key < key)
    69. 			{
    70. 				cur = cur->_right;
    71. 			}
    72. 			else if (cur->_key > key)
    73. 			{
    74. 				cur = cur->_left;
    75. 			}
    76. 			else
    77. 			{
    78. 				return true;
    79. 			}
    80. 		}
    81. 		return false;
    82. 	}
    83.  
    84. 	bool Erase(const K& key)
    85. 	{
    86. 		Node* parent = nullptr;
    87. 		Node* cur = _root;
    88.  
    89. 		while (cur)
    90. 		{
    91. 			if (cur->_key < key)
    92. 			{
    93. 				parent = cur;
    94. 				cur = cur->_right;
    95. 			}
    96. 			else if (cur->_key > key)
    97. 			{
    98. 				parent = cur;
    99. 				cur = cur->_left;
    100. 			}
    101. 			else
    102. 			{
    103. 				if (cur->_left == nullptr)
    104. 				{
    105. 					if (cur == _root)
    106. 					{
    107. 						_root = cur->_right;
    108. 					}
    109. 					else
    110. 					{
    111. 						if (parent->_right == cur)
    112. 						{
    113. 							parent->_right = cur->_right;
    114. 						}
    115. 						else
    116. 						{
    117. 							parent->_left = cur->_right;
    118. 						}
    119. 					}
    120. 				}
    121. 				else if (cur->_right == nullptr)
    122. 				{
    123. 					if (cur == _root)
    124. 					{
    125. 						_root = cur->_left;
    126. 					}
    127. 					else
    128. 					{
    129. 						if (parent->_right = cur)
    130. 						{
    131. 							parent->_right = cur->_left;
    132. 						}
    133. 						else
    134. 						{
    135. 							parent->_left = cur->_left;
    136. 						}
    137. 					}
    138. 				}
    139. 				else
    140. 				{
    141. 					Node* parent = cur;
    142. 					Node* leftMax = cur->_left;
    143. 					while (leftMax->_right)
    144. 					{
    145. 						parent = leftMax;
    146. 						leftMax = leftMax->_right;
    147. 					}
    148. 					swap(cur->_key, leftMax->_key);
    149. 					if (parent->_left == leftMax)
    150. 					{
    151. 						parent->_left = leftMax->_left;
    152. 					}
    153. 					else
    154. 					{
    155. 						parent->_right = leftMax->_left;
    156. 					}
    157. 					cur = leftMax;
    158. 				}
    159. 				delete cur;
    160. 				return true;
    161. 			}
    162. 		}
    163. 		return false;
    164. 	}
    165. 	void InOrder()
    166. 	{
    167. 		_InOrder(_root);
    168. 		cout << endl;
    169. 	}
    170. 	void _InOrder(Node* root)
    171. 	{
    172. 		if (root == nullptr)
    173. 		{
    174. 			return;
    175. 		}
    176. 		_InOrder(root->_left);
    177. 		cout << root->_key << " ";
    178. 		_InOrder(root->_right);
    179. 	}
    180. 	private:
    181. 		Node* _root;
    182. };

    四、二叉搜索树的应用

    key模型

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

    比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

    以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树；

    在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。 

    KV模型

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

    比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与对应的中文就构成一种键值对；

    再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。

    key模型和KV模型的实现：

    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. 	public:
    22. 		BSTree()
    23. 			:_root(nullptr)
    24. 		{}
    25.  
    26. 		BSTree(const BSTree& t)
    27. 		{
    28. 			_root = Copy(t._root);
    29. 		}
    30.  
    31. 		BSTree& operator=(BSTree t)
    32. 		{
    33. 			swap(_root, t._root);
    34. 			return *this;
    35. 		}
    36.  
    37. 		~BSTree()
    38. 		{
    39. 			Destroy(_root);
    40. 		}
    41.  
    42. 		bool Insert(const K& key)
    43. 		{
    44. 			if (_root == nullptr)
    45. 			{
    46. 				_root = new Node(key);
    47. 				return true;
    48. 			}
    49.  
    50. 			Node* parent = nullptr;
    51. 			Node* cur = _root;
    52. 			while (cur)
    53. 			{
    54. 				if (cur->_key < key)
    55. 				{
    56. 					parent = cur;
    57. 					cur = cur->_right;
    58. 				}
    59. 				else if (cur->_key > key)
    60. 				{
    61. 					parent = cur;
    62. 					cur = cur->_left;
    63. 				}
    64. 				else
    65. 				{
    66. 					return false;
    67. 				}
    68. 			}
    69.  
    70. 			cur = new Node(key);
    71. 			if (parent->_key < key)
    72. 			{
    73. 				parent->_right = cur;
    74. 			}
    75. 			else
    76. 			{
    77. 				parent->_left = cur;
    78. 			}
    79.  
    80. 			return true;
    81. 		}
    82.  
    83. 		bool Find(const K& key)
    84. 		{
    85. 			Node* cur = _root;
    86. 			while (cur)
    87. 			{
    88. 				if (cur->_key < key)
    89. 				{
    90. 					cur = cur->_right;
    91. 				}
    92. 				else if (cur->_key > key)
    93. 				{
    94. 					cur = cur->_left;
    95. 				}
    96. 				else
    97. 				{
    98. 					return true;
    99. 				}
    100. 			}
    101.  
    102. 			return false;
    103. 		}
    104.  
    105. 		bool Erase(const K& key)
    106. 		{
    107. 			Node* parent = nullptr;
    108. 			Node* cur = _root;
    109.  
    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. 					
    125. 					if (cur->_left == nullptr)
    126. 					{
    127. 						if (cur == _root)
    128. 						{
    129. 							_root = cur->_right;
    130. 						}
    131. 						else
    132. 						{
    133. 							if (parent->_right == cur)
    134. 							{
    135. 								parent->_right = cur->_right;
    136. 							}
    137. 							else
    138. 							{
    139. 								parent->_left = cur->_right;
    140. 							}
    141. 						}
    142. 					}
    143. 					else if (cur->_right == nullptr)
    144. 					{
    145. 						if (cur == _root)
    146. 						{
    147. 							_root = cur->_left;
    148. 						}
    149. 						else
    150. 						{
    151. 							if (parent->_right == cur)
    152. 							{
    153. 								parent->_right = cur->_left;
    154. 							}
    155. 							else
    156. 							{
    157. 								parent->_left = cur->_left;
    158. 							}
    159. 						}
    160. 					}
    161. 					else
    162. 					{
    163. 						Node* parent = cur;
    164. 						Node* leftMax = cur->_left;
    165. 						while (leftMax->_right)
    166. 						{
    167. 							parent = leftMax;
    168. 							leftMax = leftMax->_right;
    169. 						}
    170.  
    171. 						swap(cur->_key, leftMax->_key);
    172.  
    173. 						if (parent->_left == leftMax)
    174. 						{
    175. 							parent->_left = leftMax->_left;
    176. 						}
    177. 						else
    178. 						{
    179. 							parent->_right = leftMax->_left;
    180. 						}
    181.  
    182. 						cur = leftMax;
    183. 					}
    184.  
    185. 					delete cur;
    186. 					return true;
    187. 				}
    188. 			}
    189.  
    190. 			return false;
    191. 		}
    192.  
    193. 		void InOrder()
    194. 		{
    195. 			_InOrder(_root);
    196. 			cout << endl;
    197. 		}
    198.  
    199. 		bool FindR(const K& key)
    200. 		{
    201. 			return _FindR(_root, key);
    202. 		}
    203.  
    204. 		bool InsertR(const K& key)
    205. 		{
    206. 			return _InsertR(_root, key);
    207. 		}
    208.  
    209. 		bool EraseR(const K& key)
    210. 		{
    211. 			return _EraseR(_root, key);
    212. 		}
    213.  
    214. 	private:
    215. 		Node* Copy(Node* root)
    216. 		{
    217. 			if (root == nullptr)
    218. 				return nullptr;
    219.  
    220. 			Node* copyroot = new Node(root->_key);
    221. 			copyroot->_left = Copy(root->_left);
    222. 			copyroot->_right = Copy(root->_right);
    223. 			return copyroot;
    224. 		}
    225.  
    226. 		void Destroy(Node*& root)
    227. 		{
    228. 			if (root == nullptr)
    229. 				return;
    230.  
    231. 			Destroy(root->_left);
    232. 			Destroy(root->_right);
    233. 			delete root;
    234. 			root = nullptr;
    235. 		}
    236.  
    237. 		bool _EraseR(Node*& root, const K& key)
    238. 		{
    239. 			if (root == nullptr)
    240. 				return false;
    241.  
    242. 			if (root->_key < key)
    243. 			{
    244. 				return _EraseR(root->_right, key);
    245. 			}
    246. 			else if (root->_key > key)
    247. 			{
    248. 				return _EraseR(root->_left, key);
    249. 			}
    250. 			else
    251. 			{
    252. 				Node* del = root;
    253.  
    254. 				if (root->_left == nullptr)
    255. 				{
    256. 					root = root->_right;
    257. 				}
    258. 				else if (root->_right == nullptr)
    259. 				{
    260. 					root = root->_left;
    261. 				}
    262. 				else
    263. 				{
    264. 					Node* leftMax = root->_left;
    265. 					while (leftMax->_right)
    266. 					{
    267. 						leftMax = leftMax->_right;
    268. 					}
    269.  
    270. 					swap(root->_key, leftMax->_key);
    271.  
    272. 					return _EraseR(root->_left, key);
    273. 				}
    274.  
    275. 				delete del;
    276. 				return true;
    277. 			}
    278. 		}
    279.  
    280. 		bool _InsertR(Node*& root, const K& key)
    281. 		{
    282. 			if (root == nullptr)
    283. 			{
    284. 				root = new Node(key);
    285. 				return true;
    286. 			}
    287.  
    288. 			if (root->_key < key)
    289. 			{
    290. 				return _InsertR(root->_right, key);
    291. 			}
    292. 			else if (root->_key > key)
    293. 			{
    294. 				return _InsertR(root->_left, key);
    295. 			}
    296. 			else
    297. 			{
    298. 				return false;
    299. 			}
    300. 		}
    301.  
    302. 		bool _FindR(Node* root, const K& key)
    303. 		{
    304. 			if (root == nullptr)
    305. 				return false;
    306.  
    307. 			if (root->_key < key)
    308. 			{
    309. 				return _FindR(root->_right, key);
    310. 			}
    311. 			else if (root->_key > key)
    312. 			{
    313. 				return _FindR(root->_left, key);
    314. 			}
    315. 			else
    316. 			{
    317. 				return true;
    318. 			}
    319. 		}
    320.  
    321. 		void _InOrder(Node* root)
    322. 		{
    323. 			if (root == NULL)
    324. 			{
    325. 				return;
    326. 			}
    327.  
    328. 			_InOrder(root->_left);
    329. 			cout << root->_key << " ";
    330. 			_InOrder(root->_right);
    331. 		}
    332. 	private:
    333. 		Node* _root;
    334. 	};
    335.  
    336. namespace key_value
    337. {
    338. 	template<class K, class V>
    339. 	struct BSTreeNode
    340. 	{
    341. 		BSTreeNode* _left;
    342. 		BSTreeNode* _right;
    343. 		K _key;
    344. 		V _value;
    345.  
    346. 		BSTreeNode(const K& key, const V& value)
    347. 			:_left(nullptr)
    348. 			, _right(nullptr)
    349. 			, _key(key)
    350. 			, _value(value)
    351. 		{}
    352. 	};
    353.  
    354. 	template<class K, class V>
    355. 	class BSTree
    356. 	{
    357. 		typedef BSTreeNode Node;
    358. 	public:
    359. 		BSTree()
    360. 			:_root(nullptr)
    361. 		{}
    362.  
    363. 		void InOrder()
    364. 		{
    365. 			_InOrder(_root);
    366. 			cout << endl;
    367. 		}
    368.  
    369. 		Node* FindR(const K& key)
    370. 		{
    371. 			return _FindR(_root, key);
    372. 		}
    373.  
    374. 		bool InsertR(const K& key, const V& value)
    375. 		{
    376. 			return _InsertR(_root, key, value);
    377. 		}
    378.  
    379. 		bool EraseR(const K& key)
    380. 		{
    381. 			return _EraseR(_root, key);
    382. 		}
    383.  
    384. 	private:
    385. 		bool _EraseR(Node*& root, const K& key)
    386. 		{
    387. 			if (root == nullptr)
    388. 				return false;
    389.  
    390. 			if (root->_key < key)
    391. 			{
    392. 				return _EraseR(root->_right, key);
    393. 			}
    394. 			else if (root->_key > key)
    395. 			{
    396. 				return _EraseR(root->_left, key);
    397. 			}
    398. 			else
    399. 			{
    400. 				Node* del = root;
    401.  
    402. 				if (root->_left == nullptr)
    403. 				{
    404. 					root = root->_right;
    405. 				}
    406. 				else if (root->_right == nullptr)
    407. 				{
    408. 					root = root->_left;
    409. 				}
    410. 				else
    411. 				{
    412. 					Node* leftMax = root->_left;
    413. 					while (leftMax->_right)
    414. 					{
    415. 						leftMax = leftMax->_right;
    416. 					}
    417.  
    418. 					swap(root->_key, leftMax->_key);
    419.  
    420. 					return _EraseR(root->_left, key);
    421. 				}
    422.  
    423. 				delete del;
    424. 				return true;
    425. 			}
    426. 		}
    427.  
    428. 		bool _InsertR(Node*& root, const K& key, const V& value)
    429. 		{
    430. 			if (root == nullptr)
    431. 			{
    432. 				root = new Node(key, value);
    433. 				return true;
    434. 			}
    435.  
    436. 			if (root->_key < key)
    437. 			{
    438. 				return _InsertR(root->_right, key, value);
    439. 			}
    440. 			else if (root->_key > key)
    441. 			{
    442. 				return _InsertR(root->_left, key, value);
    443. 			}
    444. 			else
    445. 			{
    446. 				return false;
    447. 			}
    448. 		}
    449.  
    450. 		Node* _FindR(Node* root, const K& key)
    451. 		{
    452. 			if (root == nullptr)
    453. 				return nullptr;
    454.  
    455. 			if (root->_key < key)
    456. 			{
    457. 				return _FindR(root->_right, key);
    458. 			}
    459. 			else if (root->_key > key)
    460. 			{
    461. 				return _FindR(root->_left, key);
    462. 			}
    463. 			else
    464. 			{
    465. 				return root;
    466. 			}
    467. 		}
    468.  
    469. 		void _InOrder(Node* root)
    470. 		{
    471. 			if (root == NULL)
    472. 			{
    473. 				return;
    474. 			}
    475.  
    476. 			_InOrder(root->_left);
    477. 			cout << root->_key << ":" << root->_value << endl;
    478. 			_InOrder(root->_right);
    479. 		}
    480. 	private:
    481. 		Node* _root;
    482. 	};

  • 相关阅读:
    朔雪流量复制器的前端
    雷达编程实战之静态杂波滤除与到达角估计
    CAT1 4G+以太网开发板腾讯云手机微信小程序显示温度和下发控制
    R语言爬虫代码模版：技术原理与实践应用
    网络编程进化史：Netty Channel 的崭新篇章
    我可能永远也没办法成为全栈工程师了，看看你还差多少？
    【N年测试总结】 测试入职一家新公司的工作开展思路
    xss反射型漏洞复现
    Hive的时间操作函数
    java之线程间通信
  • 原文地址：https://blog.csdn.net/m0_60464690/article/details/133420205