devbox
小舞很执着
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉搜索树详解及代码实现_二叉搜索树代码

作者：小舞很执着 | 2024-07-31 18:05:56

赞

踩

二叉搜索树代码

目录

一、什么是二叉搜索树

 二、二叉搜索树的有关操作

2.1 查找：

2.2插入：

2.3 删除：

 2.4 打印

三、二叉搜索树的应用

3.1 K模型：

3.2 KV模型：

四、整体代码：

K模型：

KV模型：

一、什么是二叉搜索树

二叉搜索树（BST, Binary Search Tree），也称为二叉排序树或二叉查找树。

每一棵搜索树都满足如下条件：

1.非空左子树的所有键值小于其根节点的键值

2.非空右子树的所有键值大于其根节点的键值

3.左、右子树都是二叉搜索树

 如图所示二叉树：

 二、二叉搜索树的有关操作

如该树 数组表示为：int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13}; 用此树进行讲解

下面代码用到的c++类结构为：

  1. 	template<class K>  //模板
  2. 	struct BSTreeNode {
  3. 		BSTreeNode<K>* _left;
  4. 		BSTreeNode<K>* _right;
  5. 		K _key;
  6. 	private:
  7. 		Node* _root = nullptr;
  8. 	};

2.1 查找：

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。

代码实现：

非递归：

  1. 		bool Find(const K& key)  //K为模板
  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. 			return false;
  20. 		}

递归：

  1. bool _FindR(Node* root, const K& key)
  2. 		{
  3. 			if (root == nullptr)
  4. 				return false;
  5.  
  6. 			if (root->_key < key)
  7. 				return _FinfR(root->_right, key);
  8. 			else if (root->_key > key)
  9. 				return _FindR(root->_left, key);
  10. 			else
  11. 				return true;
  12. 		}

2.2插入：

插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点（大于根节点值往右走，小于根节点值往左走）。注意：二叉搜索树插入过程中，插入已存在值无意义。

为该树插入16 、9 两个值，根据搜素树应满足的“左小右大”的条件，插入后如图：

 代码实现：

非递归写法：

  1. bool Insert(const K& key)    //K为模板
  2. 		{
  3.             //空树直接插
  4. 			if (_root == nullptr)
  5. 			{
  6. 				_root = new Node(key);
  7. 				return true;
  8. 			}
  9.             //非空树
  10. 			Node* parent = nullptr;//用于存父节点，便于与插入的子节点链接
  11. 			Node* cur = _root;
  12. 			while (cur)//找到要插入的位置
  13. 			{
  14. 				if (cur->_key < key)//大于 往右子树
  15. 				{
  16. 					parent = cur;
  17. 					cur = cur->_right;
  18. 				}
  19. 				else if (cur->_key > key)//小于往左子树
  20. 				{
  21. 					parent = cur;
  22. 					cur = cur->_left;
  23. 				}
  24. 				else
  25. 				{
  26. 					return false;//遇到相同的数就不插入，相当于去重
  27. 				}
  28. 			}
  29.             //找到插入的位置后，进行插入操作
  30. 			cur = new Node(key);
  31. 			if (parent->_key < key)
  32. 			{
  33. 				parent->_right = cur;
  34. 			}
  35. 			else
  36. 			{
  37. 				parent->_left = cur;
  38. 			}
  39. 			return true;
  40. 		}

递归写法：

  1. bool _InsertR(Node*& root, const K& key) //K为模板
  2. 		{
  3. 			if (root == nullptr)
  4. 			{
  5. 				root = new Node(key);
  6. 				return true;
  7. 			}
  8.  
  9. 			if (root->_key < key)
  10. 			{
  11. 				return _InsertR(root->_right, key);
  12. 			}
  13. 			else if (root->_key > key)
  14. 			{
  15. 				return _InsertR(root->_left, key);
  16. 			}
  17. 			else
  18. 			{
  19. 				return false;
  20. 			}
  21. 		}

2.3 删除：

删除某一节点可分为四种情况：

a.要删除节点没有孩子节点

如图删除节点值13，没有孩子节点，删除后父节点parent->left就指向空。

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

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

该两种情况相似。如删除节点14后，其孩子节点13的父节点就变为10，即：10->right=13

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

该情况难点在于删除节点后，被删除节点的父节点应该链接被删除节点的哪个孩子节点。这分为两种方法：

1.连接删除节点的左子树中最右边节点

2.连接删除节点的右子树中最左节点

一般情况下，我们使用方法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. 					//删除位置左空
  21. 					if (cur->_left == nullptr)
  22. 					{
  23. 						if (cur == _root)//删除位置在根处
  24. 						{
  25. 							_root = cur->_right;
  26. 						}
  27. 						else
  28. 						{
  29. 							//找到当前位置后且左空，且位于parent的左，
  30. 							//则删除该位置后的parent左就变为cur的右
  31. 							//如果当前位置位于parren右，且且左空，则paret的右即为cur的右
  32. 							if (cur == parent->_left)
  33. 							{
  34. 								parent->_left = cur->_right;
  35. 							}
  36. 							else
  37. 							{
  38. 								parent->_right = cur->_right;
  39. 							}
  40. 						}
  41. 						delete cur;
  42. 						cur == nullptr;
  43. 					}
  44. 					else if (cur->_right == nullptr)//删除位置右空
  45. 					{
  46. 						if (cur == _root)
  47. 						{
  48. 							_root = cur->_left;
  49. 						}
  50. 						else
  51. 						{
  52. 							if (cur == parent->_left)
  53. 							{
  54. 								parent->_left = cur->_left;
  55. 							}
  56. 							else
  57. 							{
  58. 								parent->_right = cur->_left;
  59. 							}
  60. 						}
  61. 						delete cur;
  62. 						cur = nullptr;
  63. 					}
  64. 					else//左右都不为空
  65. 					{
  66. 						//替换法删除  //右子树最小节点---右子树最左节点
  67. 						Node* minparent = cur;
  68. 						Node* min = cur->_right;
  69. 						while (min->_left)
  70. 						{
  71. 							minparent = min;
  72. 							min = min->_left;
  73. 						}
  74. 						swap(cur->_key, min->_key);
  75. 						if (minparent->_left == min)
  76. 							minparent->_left = min->_right;
  77. 						else
  78. 							minparent->_right = min->_right;
  79. 						delete min;
  80. 					}
  81. 					return true;
  82. 				}
  83. 			}
  84. 			return false;
  85. 		}

递归：

  1. bool _EraseR(Node*& root, const K& key)
  2. 		{
  3. 			if (root == nullptr)
  4. 			{
  5. 				return false;
  6. 			}
  7.  
  8. 			if (root->_key < key)
  9. 			{
  10. 				return _EraseR(root->_right, key);
  11. 			}
  12. 			else if (root->_key > key)
  13. 			{
  14. 				return _EraseR(root->_left, key);
  15. 			}
  16. 			else
  17. 			{
  18. 				Node* del = root;
  19. 				if (root->_left == nullptr)
  20. 				{
  21. 					root = root->_right;
  22. 				}
  23. 				else if (root->_right == nullptr)
  24. 				{
  25. 					root = root->_left;
  26. 				}
  27. 				else
  28. 				{
  29. 					//找右数的最左节点
  30. 					Node* min = root->_right;
  31. 					while (min->_left)
  32. 					{
  33. 						min = min->_left;
  34. 					}
  35. 					swap(root->_key, min->_key);
  36. 					return _EraseR(root->_right, key);
  37. 				}
  38.  
  39. 				delete del;
  40. 				return true;
  41. 			}
  42. 		}

 2.4 打印

这里可以将创建的二叉搜索树通过中序（左->根->右）打印出来，就是由小到大的升序序列。因为二叉搜索树中不能有重复的数值，所以可以通过插入一组数据实现对其排序且去重。

  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. 		}

该二叉搜索树的整体代码放在文末。

三、二叉搜索树的应用

3.1 K模型：

上面我们所实现的就是K模型。

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到
的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树，在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

3.2 KV模型：

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。一般可以通过查找关键码key来查找对应的值。

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文<word, chinese>就构成一种键值对。（KV模型整体代码与K模型思想很相似，就直接放在文末）

  1. 	void TestBSTree1()
  2. 	{
  3. 		BSTree<string, string> dict;
  4. 		dict.Insert("sort", "排序");
  5. 		dict.Insert("left", "左边");
  6. 		dict.Insert("right", "右边");
  7. 		dict.Insert("string", "字符串");
  8. 		dict.Insert("insert", "插入");
  9. 		string str;
  10. 		while (cin >> str)
  11. 		{
  12. 			BSTreeNode<string, string>* ret = dict.Find(str);
  13. 			if (ret)
  14. 			{
  15. 				cout << ":" << ret->_value << endl;
  16. 			}
  17. 			else
  18. 			{
  19. 				cout << "->无此单词" << endl;
  20. 			}
  21. 		}
  22. 	}

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

  1. void TestBSTree2()
  2. 	{
  3. 		string arr[] = { "苹果","苹果" ,"香蕉" ,"草莓" ,"香蕉" ,"苹果" ,"苹果", "苹果" };
  4. 		
  5. 		BSTree<string, int> countTree;
  6. 		for (auto& str:arr)
  7. 		{
  8. 			auto ret = countTree.Find(str);
  9. 			if (ret)
  10. 			{
  11. 				ret->_value++;
  12. 			}
  13. 			else
  14. 			{
  15. 				countTree.Insert(str, 1);
  16. 			}
  17. 		}
  18.  
  19. 		countTree.InOrder();
  20. 	}

四、整体代码：

K模型：

  1. namespace key
  2. {
  3. 	template<class K>
  4. 	struct BSTreeNode {
  5. 		BSTreeNode<K>* _left;
  6. 		BSTreeNode<K>* _right;
  7. 		K _key;
  8.  
  9. 		BSTreeNode(const K& key)
  10. 			:_left(nullptr)
  11. 			, _right(nullptr)
  12. 			, _key(key)
  13. 		{}
  14. 	};
  15.  
  16.  
  17. 	//BinarySearchTree
  18. 	template<class K>   //Key
  19. 	class BSTree {
  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.  
  30. 			Node* parent = nullptr;
  31. 			Node* cur = _root;
  32. 			while (cur)//找到要插入的位置
  33. 			{
  34. 				if (cur->_key < key)
  35. 				{
  36. 					parent = cur;
  37. 					cur = cur->_right;
  38. 				}
  39. 				else if (cur->_key > key)
  40. 				{
  41. 					parent = cur;
  42. 					cur = cur->_left;
  43. 				}
  44. 				else
  45. 				{
  46. 					return false;//遇到相同的数就不插入，相当于去重
  47. 				}
  48. 			}
  49. 			cur = new Node(key);
  50. 			if (parent->_key < key)
  51. 			{
  52. 				parent->_right = cur;
  53. 			}
  54. 			else
  55. 			{
  56. 				parent->_left = cur;
  57. 			}
  58. 			return true;
  59. 		}
  60. 		bool Find(const K& key)
  61. 		{
  62. 			Node* cur = _root;
  63. 			while (cur)
  64. 			{
  65. 				if (cur->_key < key)
  66. 				{
  67. 					cur = cur->_right;
  68. 				}
  69. 				else if (cur->_key > key)
  70. 				{
  71. 					cur = cur->_left;
  72. 				}
  73. 				else
  74. 				{
  75. 					return true;
  76. 				}
  77. 			}
  78. 			return false;
  79. 		}
  80.  
  81. 		bool Erase(const K& key)
  82. 		{
  83. 			Node* parent = nullptr;
  84. 			Node* cur = _root;
  85. 			while (cur)
  86. 			{
  87. 				if (cur->_key < key)
  88. 				{
  89. 					parent = cur;
  90. 					cur = cur->_right;
  91. 				}
  92. 				else if (cur->_key > key)
  93. 				{
  94. 					parent = cur;
  95. 					cur = cur->_left;
  96. 				}
  97. 				else
  98. 				{
  99. 					//开始删除
  100. 					//删除位置左空
  101. 					if (cur->_left == nullptr)
  102. 					{
  103. 						if (cur == _root)//删除位置在根处
  104. 						{
  105. 							_root = cur->_right;
  106. 						}
  107. 						else
  108. 						{
  109. 							//找到当前位置后且左空，且位于parent的左，
  110. 							//则删除该位置后的parent左就变为cur的右
  111. 							//如果当前位置位于parren右，且且左空，则paret的右即为cur的右
  112. 							if (cur == parent->_left)
  113. 							{
  114. 								parent->_left = cur->_right;
  115. 							}
  116. 							else
  117. 							{
  118. 								parent->_right = cur->_right;
  119. 							}
  120. 						}
  121. 						delete cur;
  122. 						cur == nullptr;
  123. 					}
  124. 					else if (cur->_right == nullptr)//删除位置右空
  125. 					{
  126. 						if (cur == _root)
  127. 						{
  128. 							_root = cur->_left;
  129. 						}
  130. 						else
  131. 						{
  132. 							if (cur == parent->_left)
  133. 							{
  134. 								parent->_left = cur->_left;
  135. 							}
  136. 							else
  137. 							{
  138. 								parent->_right = cur->_left;
  139. 							}
  140. 						}
  141. 						delete cur;
  142. 						cur = nullptr;
  143. 					}
  144. 					else//左右都不为空
  145. 					{
  146. 						//替换法删除  //右子树最小节点---右子树最左节点
  147. 						Node* minparent = cur;
  148. 						Node* min = cur->_right;
  149. 						while (min->_left)
  150. 						{
  151. 							minparent = min;
  152. 							min = min->_left;
  153. 						}
  154. 						swap(cur->_key, min->_key);
  155. 						if (minparent->_left == min)
  156. 							minparent->_left = min->_right;
  157. 						else
  158. 							minparent->_right = min->_right;
  159. 						delete min;
  160. 					}
  161. 					return true;
  162. 				}
  163. 			}
  164. 			return false;
  165. 		}
  166.  
  167. 		void InOrder()
  168. 		{
  169. 			_InOrder(_root);//这里套一层就可以直接使用_root;或者也可以写getroot方法
  170. 			cout << endl;
  171. 		}
  172.  
  173. 		//递归查找
  174. 		bool FindR(const K& key)
  175. 		{
  176. 			return _FindR(_root, key);
  177. 		}
  178. 		//递归插
  179. 		bool InsertR(const K& key)
  180. 		{
  181. 			return _InsertR(_root, key);
  182. 		}
  183. 		//递归删
  184. 		bool EraseR(const K& key)
  185. 		{
  186. 			return _EraseR(_root, key);
  187. 		}
  188.  
  189. 		~BSTree()
  190. 		{
  191. 			_Destroy(_root);
  192. 		}
  193. 		//强制编译器生成默认的构造
  194. 		BSTree() = default;
  195. 		BSTree(const BSTree<K>& t)
  196. 		{
  197. 			_root = _copy(t._root);
  198. 		}
  199.  
  200. 		BSTree<K>& operator=(BSTree<K> t)
  201. 		{
  202. 			swap(_root, t._root);
  203. 			return *this;
  204. 		}
  205. 	private:
  206. 		Node* _copy(Node* root)
  207. 		{
  208. 			if (root == nullptr)
  209. 			{
  210. 				return nullptr;
  211. 			}
  212. 			Node* copyRoot = new Node(root->_key);
  213. 			copyRoot->_left = _copy(root->_left);
  214. 			copyRoot->_right = _copy(root->_right);
  215. 			return copyRoot;
  216. 		}
  217. 		void _Destroy(Node*& root)
  218. 		{
  219. 			if (root == nullptr)
  220. 			{
  221. 				return;
  222. 			}
  223. 			_Destroy(root->_left);
  224. 			_Destroy(root->_right);
  225. 			delete root;
  226. 			root = nullptr;
  227. 		}
  228. 		bool _EraseR(Node*& root, const K& key)
  229. 		{
  230. 			if (root == nullptr)
  231. 			{
  232. 				return false;
  233. 			}
  234.  
  235. 			if (root->_key < key)
  236. 			{
  237. 				return _EraseR(root->_right, key);
  238. 			}
  239. 			else if (root->_key > key)
  240. 			{
  241. 				return _EraseR(root->_left, key);
  242. 			}
  243. 			else
  244. 			{
  245. 				Node* del = root;
  246. 				if (root->_left == nullptr)
  247. 				{
  248. 					root = root->_right;
  249. 				}
  250. 				else if (root->_right == nullptr)
  251. 				{
  252. 					root = root->_left;
  253. 				}
  254. 				else
  255. 				{
  256. 					//找右数的最左节点
  257. 					Node* min = root->_right;
  258. 					while (min->_left)
  259. 					{
  260. 						min = min->_left;
  261. 					}
  262. 					swap(root->_key, min->_key);
  263. 					return _EraseR(root->_right, key);//很巧妙
  264. 				}
  265.  
  266. 				delete del;
  267. 				return true;
  268. 			}
  269. 		}
  270. 		bool _InsertR(Node*& root, const K& key)
  271. 		{
  272. 			if (root == nullptr)
  273. 			{
  274. 				root = new Node(key);
  275. 				return true;
  276. 			}
  277.  
  278. 			if (root->_key < key)
  279. 			{
  280. 				return _InsertR(root->_right, key);
  281. 			}
  282. 			else if (root->_key > key)
  283. 			{
  284. 				return _InsertR(root->_left, key);
  285. 			}
  286. 			else
  287. 			{
  288. 				return false;
  289. 			}
  290. 		}
  291. 		bool _FindR(Node* root, const K& key)
  292. 		{
  293. 			if (root == nullptr)
  294. 				return false;
  295.  
  296. 			if (root->_key < key)
  297. 				return _FinfR(root->_right, key);
  298. 			else if (root->_key > key)
  299. 				return _FindR(root->_left, key);
  300. 			else
  301. 				return true;
  302. 		}
  303. 		//中序  //
  304. 		void _InOrder(Node* root)
  305. 		{
  306. 			if (root == nullptr)
  307. 			{
  308. 				return;
  309. 			}
  310. 			_InOrder(root->_left);
  311. 			cout << root->_key << " ";
  312. 			_InOrder(root->_right);
  313.  
  314. 		}
  315. 	private:
  316. 		Node* _root = nullptr;
  317. 	};
  318. }

KV模型：

  1. template<class K,class V>
  2. 	struct BSTreeNode {
  3. 		BSTreeNode<K,V>* _left;
  4. 		BSTreeNode<K,V>* _right;
  5. 		K _key;
  6. 		V _value;
  7.  
  8. 		BSTreeNode(const K& key, const V& value)
  9. 			:_left(nullptr)
  10. 			, _right(nullptr)
  11. 			, _key(key)
  12. 			, _value(value)
  13. 		{}
  14. 	};
  15.  
  16. 	template<class K,class V>   //
  17. 	class BSTree {
  18. 		typedef BSTreeNode<K,V> Node;
  19. 	public:
  20. 		bool Insert(const K& key,const V& value)
  21. 		{
  22. 			if (_root == nullptr)
  23. 			{
  24. 				_root = new Node(key,value);
  25. 				return true;
  26. 			}
  27.  
  28. 			Node* parent = nullptr;
  29. 			Node* cur = _root;
  30. 			while (cur)//找到要插入的位置
  31. 			{
  32. 				if (cur->_key < key)
  33. 				{
  34. 					parent = cur;
  35. 					cur = cur->_right;
  36. 				}
  37. 				else if (cur->_key > key)
  38. 				{
  39. 					parent = cur;
  40. 					cur = cur->_left;
  41. 				}
  42. 				else
  43. 				{
  44. 					return false;//遇到相同的数就不插入，相当于去重
  45. 				}
  46. 			}
  47. 			cur = new Node(key,value);
  48. 			if (parent->_key < key)
  49. 			{
  50. 				parent->_right = cur;
  51. 			}
  52. 			else
  53. 			{
  54. 				parent->_left = cur;
  55. 			}
  56. 			return true;
  57. 		}
  58. 		Node* Find(const K& key)
  59. 		{
  60. 			Node* cur = _root;
  61. 			while (cur)
  62. 			{
  63. 				if (cur->_key < key)
  64. 				{
  65. 					cur = cur->_right;
  66. 				}
  67. 				else if (cur->_key > key)
  68. 				{
  69. 					cur = cur->_left;
  70. 				}
  71. 				else
  72. 				{
  73. 					return cur;
  74. 				}
  75. 			}
  76. 			return nullptr;
  77. 		}
  78.  
  79. 		bool Erase(const K& key)
  80. 		{
  81. 			Node* parent = nullptr;
  82. 			Node* cur = _root;
  83. 			while (cur)
  84. 			{
  85. 				if (cur->_key < key)
  86. 				{
  87. 					parent = cur;
  88. 					cur = cur->_right;
  89. 				}
  90. 				else if (cur->_key > key)
  91. 				{
  92. 					parent = cur;
  93. 					cur = cur->_left;
  94. 				}
  95. 				else
  96. 				{
  97. 					//开始删除
  98. 					//删除位置左空
  99. 					if (cur->_left == nullptr)
  100. 					{
  101. 						if (cur == _root)//删除位置在根处
  102. 						{
  103. 							_root = cur->_right;
  104. 						}
  105. 						else
  106. 						{
  107. 							//找到当前位置后且左空，且位于parent的左，
  108. 							//则删除该位置后的parent左就变为cur的右
  109. 							//如果当前位置位于parren右，且且左空，则paret的右即为cur的右
  110. 							if (cur == parent->_left)
  111. 							{
  112. 								parent->_left = cur->_right;
  113. 							}
  114. 							else
  115. 							{
  116. 								parent->_right = cur->_right;
  117. 							}
  118. 						}
  119. 						delete cur;
  120. 						cur == nullptr;
  121. 					}
  122. 					else if (cur->_right == nullptr)//删除位置右空
  123. 					{
  124. 						if (cur == _root)
  125. 						{
  126. 							_root = cur->_left;
  127. 						}
  128. 						else
  129. 						{
  130. 							if (cur == parent->_left)
  131. 							{
  132. 								parent->_left = cur->_left;
  133. 							}
  134. 							else
  135. 							{
  136. 								parent->_right = cur->_left;
  137. 							}
  138. 						}
  139. 						delete cur;
  140. 						cur = nullptr;
  141. 					}
  142. 					else//左右都不为空
  143. 					{
  144. 						//替换法删除  //右子树最小节点---右子树最左节点
  145. 						Node* minparent = cur;
  146. 						Node* min = cur->_right;
  147. 						while (min->_left)
  148. 						{
  149. 							minparent = min;
  150. 							min = min->_left;
  151. 						}
  152. 						swap(cur->_key, min->_key);
  153. 						if (minparent->_left == min)
  154. 							minparent->_left = min->_right;
  155. 						else
  156. 							minparent->_right = min->_right;
  157. 						delete min;
  158. 					}
  159. 					return true;
  160. 				}
  161. 			}
  162.  
  163. 			//删除的中间过程都一样
  164. 			return true;
  165. 		}
  166.  
  167. 		void InOrder()
  168. 		{
  169. 			_InOrder(_root);//这里套一层就可以直接使用_root;或者也可以写getroot方法
  170. 			cout << endl;
  171. 		}
  172.  
  173. 	private:
  174. 		//中序  //
  175. 		void _InOrder(Node* root)
  176. 		{
  177. 			if (root == nullptr)
  178. 			{
  179. 				return;
  180. 			}
  181. 			_InOrder(root->_left);
  182. 			cout << root->_key << " value: " << root->_value << endl;;
  183. 			_InOrder(root->_right);
  184.  
  185. 		}
  186. 	private:
  187. 		Node* _root = nullptr;
  188. 	};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/910098
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号