二叉搜尋樹的定義
二叉搜尋樹，也稱有序二叉樹,排序二叉樹，是指一棵空樹或者具有下列性質的二叉樹：
1. 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
2. 若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
3. 任意節點的左、右子樹也分别為二叉查找樹。
4. 沒有鍵值相等的節點。
二叉搜尋樹的删除：
具體實作過程解析：
二叉搜尋樹的結構實作：
查找實作有疊代和遞歸兩種
[cpp]
view plain
copy
1. //二叉搜尋樹結構
2. template<class K, class V>
3. struct BSTreeNode
4. {
5. BSTreeNode* _left;
6. BSTreeNode* _right;
7. K _key;
8. V _value;
9.
10. const K& key, const V& value)
11. :_left(NULL)
12. ,_right(NULL)
13. ,_key(key)
14. ,_value(value)
15. {}
16.
17. }; 疊代法：
[cpp]
view plain
copy
1. //在二叉搜尋樹中查找節點
2. Node* Find(const K& key)
3. {
4. Node* cur=_root;
5. //開始周遊查找
6. while (cur)
7. {
8. if (cur->_key > key)
9. {
10. cur = cur->_left;
11. }
12. else if(cur->_key<key)
13. {
14. cur = cur->_right;
15. }
16. else
17. {
18. return cur;
19. }
20. }
21.
22. return NULL;
23. } 遞歸法：
[cpp]
view plain
copy
1. //遞歸查找法
2. Node* _Find_R(Node* root, const K& key)
3. {
4. if (root == NULL)
5. {
6. return NULL;
7. }
8. if (root->_key > key)
9. {
10. return _Find_R(root->_left, key);
11. }
12. else if (root->_key < key)
13. {
14. return _Find_R(root->_right, key);
15. }
16. else
17. {
18. return root;
19. }
20. } 删除疊代法：
[cpp]
view plain
copy
//在二叉搜尋樹中删除節點1. bool Remove(const K& key)
2. {
3. //沒有節點
4. if (_root == NULL)
5. {
6. return false;
7. }
8. //隻有一個節點
9. if (_root->_left == NULL&&_root->_right == NULL)
10. {
11. if (_root->_key == key)
12. {
13. delete _root;
14. _root = NULL;
15. return true;
16. }
17.
18. return false;
19. }
20.
21. Node* parent = NULL;
22. Node* cur = _root;
23. //周遊查找要删除節點的位置
24. while (cur)
25. {
26. Node* del = NULL;
27. if (cur->_key > key)
28. {
29. parent = cur;
30. cur = cur->_left;
31. }
32. else if (cur->_key < key)
33. {
34. parent = cur;
35. cur = cur->_right;
36. }
37. else
38. {
39. //要删除節點的左子樹為空，分3種情況
40. if (cur->_left == NULL)
41. {
42. //注意判斷父節點是否為空，若為空，則要删除的節點為根節點,如：隻有根節點5和其右節點9
43. if (parent == NULL)
44. {
45. _root = cur->_right;
46. delete cur;
47. cur = NULL;
48. return true;
49. }
50. if (parent->_key > cur->_key)
51. {
52. del = cur;
53. parent->_left = cur->_right;
54. delete del;
55. return true;
56. }
57. else if (parent->_key < key)
58. {
59. del = cur;
60. parent->_right = cur->_right;
61. delete del;
62. return true;
63. }
64. }
65. //要删除節點的右子樹為空，同樣分3種情況
66. else if (cur->_right == NULL)
67. {
68. //注意判斷父節點是否為空，若為空，則要删除的節點為根節點,如：隻有根節點5和其左節點3
69. if (parent == NULL)
70. {
71. _root = cur->_left;
72. delete cur;
73. cur = NULL;
74. return true;
75. }
76. if (parent->_key > cur->_key)
77. {
78. del = cur;
79. parent->_left = cur->_left;
80. delete del;
81. return true;
82. }
83. else if (parent->_key < cur->_key)
84. {
85. del = cur;
86. parent->_right = cur->_left;
87. delete del;
88. return true;
89. }
90. }
91. //左右子樹都不為空
92. else
93. {
94. Node* del = cur;
95. Node* parent = NULL;
96. Node* RightFirst = cur->_right;
97. //右邊第一個節點的左子樹為空
98. if (RightFirst->_left == NULL)
99. {
100. swap(RightFirst->_key, cur->_key);
101. swap(RightFirst->_value, cur->_value);
102. del = RightFirst;
103. cur->_right = RightFirst->_right;
104. delete del;
105. return true;
106. }
107. //右邊第一個節點的左子樹不為空
108. while (RightFirst->_left)
109. {
110. parent = RightFirst;
111. RightFirst = RightFirst->_left;
112. }
113. swap(RightFirst->_key, cur->_key);
114. swap(RightFirst->_value, cur->_value);
115. del = RightFirst;
116. parent->_left = RightFirst->_right;
117. delete del;
118. return true;
119. }
120. }
121. }
122. return false;
123. } 删除遞歸法：
插入非遞歸：
[cpp]
view plain
copy
bool _Remove_R(Node*& root, const K& key)1. {
2. //沒有節點
3. if (root == NULL)
4. {
5. return false;
6. }
7. //隻有一個節點
8. if (root->_left == NULL&&root->_right == NULL)
9. {
10. if (root->_key == key)
11. {
12. delete root;
13. root = NULL;
14. return true;
15. }
16. else
17. {
18. return false;
19. }
20.
21. }
22.
23. //删除二叉搜尋樹節點的遞歸寫法
24. if (root->_key > key)
25. {
26. _Remove_R(root->_left, key);
27. }
28. else if (root->_key < key)
29. {
30. _Remove_R(root->_right, key);
31. }
32. else
33. {
34. Node* del = NULL;
35.
36. if (root->_left == NULL)
37. {
38. del = root;
39. root = root->_right;
40. delete del;
41. del = NULL;
42. return true;
43. }
44. else if (root->_right == NULL)
45. {
46. del = root;
47. root = root->_left;
48. delete del;
49. del = NULL;
50. return true;
51. }
52. else
53. {
54. Node* RightFirst = root->_right;
55.
56. while (RightFirst->_left)
57. {
58. RightFirst = RightFirst->_left;
59. }
60.
61. swap(root->_key, RightFirst->_key);
62. swap(root->_value, RightFirst->_value);
63.
64. _Remove_R(root->_right, key);
65. return true;
66. }
67. }
68. } 插入遞歸：
[cpp]
view plain
copy
1. //在二叉搜尋樹中插入節點
2. bool Insert(const K& key, const V& value)
3. {
4. if (_root == NULL)
5. {
6. new Node(key, value);
7. }
8.
9. Node* cur=_root;
10. Node* parent = NULL;
11. //首先找到要插入的位置
12. while (cur)
13. {
14. if (cur->_key > key)
15. {
16. parent = cur;
17. cur = cur->_left;
18. }
19. else if(cur->_key<key)
20. {
21. parent = cur;
22. cur = cur->_right;
23. }
24. else
25. {
26. return false;
27. }
28. }
29. //在找到插入位置以後，判斷插入父親節點的左邊還是右邊
30. if (parent->_key > key)
31. {
32. new Node(key, value);
33. }
34. else
35. {
36. new Node(key, value);
37. }
38.
39. return true;
40. } [cpp]
view plain
copy
1. //遞歸插入法
2. bool _Insert_R(Node*& root, const K& key, const V& value)
3. {
4. if (root == NULL)
5. {
6. new Node(key, value);
7. return true;
8. }
9. if (root->_key > key)
10. {
11. return _Insert_R(root->_left, key, value);
12. }
13. else if(root->_key < key)
14. {
15. return _Insert_R(root->_right, key, value);
16. }
17. else
18. {
19. return false;
20. }
21. } 當二叉搜尋樹出現如下圖情形時，效率最低：
完整代碼及測試實作如下:
運作結果：
[cpp]
view plain
copy
1. #include<iostream>
2. using namespace std;
3.
4. //二叉搜尋樹結構
5. template<class K, class V>
6. struct BSTreeNode
7. {
8. BSTreeNode* _left;
9. BSTreeNode* _right;
10. K _key;
11. V _value;
12.
13. const K& key, const V& value)
14. :_left(NULL)
15. ,_right(NULL)
16. ,_key(key)
17. ,_value(value)
18. {}
19.
20. };
21.
22. template<class K,class V>
23. class BSTree
24. {
25. typedef BSTreeNode<K, V> Node;
26. public:
27. BSTree()
28. :_root(NULL)
29. {}
30.
31. //在二叉搜尋樹中插入節點
32. bool Insert(const K& key, const V& value)
33. {
34. if (_root == NULL)
35. {
36. new Node(key, value);
37. }
38.
39. Node* cur=_root;
40. Node* parent = NULL;
41. //首先找到要插入的位置
42. while (cur)
43. {
44. if (cur->_key > key)
45. {
46. parent = cur;
47. cur = cur->_left;
48. }
49. else if(cur->_key<key)
50. {
51. parent = cur;
52. cur = cur->_right;
53. }
54. else
55. {
56. return false;
57. }
58. }
59. //在找到插入位置以後，判斷插入父親節點的左邊還是右邊
60. if (parent->_key > key)
61. {
62. new Node(key, value);
63. }
64. else
65. {
66. new Node(key, value);
67. }
68.
69. return true;
70. }
71.
72.
73. //在二叉搜尋樹中查找節點
74. const K& key)
75. {
76. Node* cur=_root;
77. //開始周遊查找
78. while (cur)
79. {
80. if (cur->_key > key)
81. {
82. cur = cur->_left;
83. }
84. else if(cur->_key<key)
85. {
86. cur = cur->_right;
87. }
88. else
89. {
90. return cur;
91. }
92. }
93.
94. return NULL;
95. }
96.
97.
98. //在二叉搜尋樹中删除節點
99. bool Remove(const K& key)
100. {
101. //沒有節點
102. if (_root == NULL)
103. {
104. return false;
105. }
106. //隻有一個節點
107. if (_root->_left == NULL&&_root->_right == NULL)
108. {
109. if (_root->_key == key)
110. {
111. delete _root;
112. _root = NULL;
113. return true;
114. }
115.
116. return false;
117. }
118.
119. Node* parent = NULL;
120. Node* cur = _root;
121. //周遊查找要删除節點的位置
122. while (cur)
123. {
124. Node* del = NULL;
125. if (cur->_key > key)
126. {
127. parent = cur;
128. cur = cur->_left;
129. }
130. else if (cur->_key < key)
131. {
132. parent = cur;
133. cur = cur->_right;
134. }
135. else
136. {
137. //要删除節點的左子樹為空，分3種情況
138. if (cur->_left == NULL)
139. {
140. //注意判斷父節點是否為空，若為空，則要删除的節點為根節點,如：隻有根節點5和其右節點9
141. if (parent == NULL)
142. {
143. _root = cur->_right;
144. delete cur;
145. cur = NULL;
146. return true;
147. }
148. if (parent->_key > cur->_key)
149. {
150. del = cur;
151. parent->_left = cur->_right;
152. delete del;
153. return true;
154. }
155. else if (parent->_key < key)
156. {
157. del = cur;
158. parent->_right = cur->_right;
159. delete del;
160. return true;
161. }
162. }
163. //要删除節點的右子樹為空，同樣分3種情況
164. else if (cur->_right == NULL)
165. {
166. //注意判斷父節點是否為空，若為空，則要删除的節點為根節點,如：隻有根節點5和其左節點3
167. if (parent == NULL)
168. {
169. _root = cur->_left;
170. delete cur;
171. cur = NULL;
172. return true;
173. }
174. if (parent->_key > cur->_key)
175. {
176. del = cur;
177. parent->_left = cur->_left;
178. delete del;
179. return true;
180. }
181. else if (parent->_key < cur->_key)
182. {
183. del = cur;
184. parent->_right = cur->_left;
185. delete del;
186. return true;
187. }
188. }
189. //左右子樹都不為空
190. else
191. {
192. Node* del = cur;
193. Node* parent = NULL;
194. Node* RightFirst = cur->_right;
195. //右邊第一個節點的左子樹為空
196. if (RightFirst->_left == NULL)
197. {
198. swap(RightFirst->_key, cur->_key);
199. swap(RightFirst->_value, cur->_value);
200. del = RightFirst;
201. cur->_right = RightFirst->_right;
202. delete del;
203. return true;
204. }
205. //右邊第一個節點的左子樹不為空
206. while (RightFirst->_left)
207. {
208. parent = RightFirst;
209. RightFirst = RightFirst->_left;
210. }
211. swap(RightFirst->_key, cur->_key);
212. swap(RightFirst->_value, cur->_value);
213. del = RightFirst;
214. parent->_left = RightFirst->_right;
215. delete del;
216. return true;
217. }
218. }
219. }
220. return false;
221. }
222.
223. bool Insert_R(const K& key, const V& value)
224. {
225. return _Insert_R(_root, key, value);
226. }
227.
228. const K& key)
229. {
230. return _Find_R(_root, key);
231. }
232.
233. bool Remove_R(const K& key)
234. {
235. return _Remove_R(_root, key);
236. }
237.
238. void InOrder()
239. {
240. _InOrder(_root);
241. cout << endl;
242. }
243.
244. protected:
245.
246. bool _Remove_R(Node*& root, const K& key)
247. {
248. //沒有節點
249. if (root == NULL)
250. {
251. return false;
252. }
253. //隻有一個節點
254. if (root->_left == NULL&&root->_right == NULL)
255. {
256. if (root->_key == key)
257. {
258. delete root;
259. root = NULL;
260. return true;
261. }
262. else
263. {
264. return false;
265. }
266.
267. }
268.
269. //删除二叉搜尋樹節點的遞歸寫法
270. if (root->_key > key)
271. {
272. _Remove_R(root->_left, key);
273. }
274. else if (root->_key < key)
275. {
276. _Remove_R(root->_right, key);
277. }
278. else
279. {
280. Node* del = NULL;
281.
282. if (root->_left == NULL)
283. {
284. del = root;
285. root = root->_right;
286. delete del;
287. del = NULL;
288. return true;
289. }
290. else if (root->_right == NULL)
291. {
292. del = root;
293. root = root->_left;
294. delete del;
295. del = NULL;
296. return true;
297. }
298. else
299. {
300. Node* RightFirst = root->_right;
301.
302. while (RightFirst->_left)
303. {
304. RightFirst = RightFirst->_left;
305. }
306.
307. swap(root->_key, RightFirst->_key);
308. swap(root->_value, RightFirst->_value);
309.
310. _Remove_R(root->_right, key);
311. return true;
312. }
313. }
314. }
315.
316. //遞歸查找法
317. const K& key)
318. {
319. if (root == NULL)
320. {
321. return NULL;
322. }
323. if (root->_key > key)
324. {
325. return _Find_R(root->_left, key);
326. }
327. else if (root->_key < key)
328. {
329. return _Find_R(root->_right, key);
330. }
331. else
332. {
333. return root;
334. }
335. }
336.
337. //遞歸插入法
338. bool _Insert_R(Node*& root, const K& key, const V& value)
339. {
340. if (root == NULL)
341. {
342. new Node(key, value);
343. return true;
344. }
345. if (root->_key > key)
346. {
347. return _Insert_R(root->_left, key, value);
348. }
349. else if(root->_key < key)
350. {
351. return _Insert_R(root->_right, key, value);
352. }
353. else
354. {
355. return false;
356. }
357. }
358.
359. void _InOrder(Node* root)
360. {
361. if (root == NULL)
362. {
363. return;
364. }
365.
366. _InOrder(root->_left);
367. " ";
368. _InOrder(root->_right);
369. }
370. protected:
371. Node* _root;
372.
373. };
374.
375.
376. void Test()
377. {
378. int, int> s;
379.
380. //測試插入
381. s.Insert_R(5, 1);
382. s.Insert_R(4, 1);
383. s.Insert_R(3, 1);
384. s.Insert_R(6, 1);
385. s.Insert_R(1, 1);
386. s.Insert_R(2, 1);
387. s.Insert_R(0, 1);
388. s.Insert_R(9, 1);
389. s.Insert_R(8, 1);
390. s.Insert_R(7, 1);
391.
392. //二叉搜尋樹按中序輸出是有序的
393. s.InOrder();
394.
395. //測試查找
396. cout << s.Find_R(6)->_key << endl;
397.
398. //測試删除
399. s.Remove(4);
400. s.Remove(6);
401. s.Remove(3);
402. s.Remove(1);
403. s.Remove(2);
404.
405. //再次列印删除後的結果
406. s.InOrder();
407.
408. }
409.
410. int main()
411. {
412. Test();
413. "pause");
414. return 0;
415. } 0 1 2 3 4 5 6 7 8 9
6
0 5 7 8 9