【算法導論】二叉查找樹的操作C++實現

本代碼為算法導論第12章中，偽代碼的C++實現：

1. #include <iostream>
2. #include <vector>
3. using namespace std;
4. /*二叉查找樹結構*/
5. typedef struct BSTree
6. {
7. int node_value;
8. struct BSTree * left;
9. struct BSTree * right;
10. struct BSTree * parent;
11. }Tree;
12. Tree * root = NULL;
13. /*****構造二叉查找樹**********************************************/
14. void CreateBSTree(Tree * root,int node_value);
15. Tree * CreateBSTree(int * array_list,int array_length);
17. void Print(Tree* root);
19. /***************************************************************/
20. int Minimum(Tree * p);
21. Tree * TreeMinimum(Tree * root);
22. int Maximum(Tree * p);
23. Tree * TreeMaximum(Tree * root);
24. Tree * FindNode(Tree * root,int node_value);
25. Tree * Successor(Tree * root);
26. Tree * PredeSuccessor(Tree * p);
27. bool DeleteTreeNode(Tree * root,int node_value);
28. bool DeleteTreeNode(Tree * n);
29. /***************************************************************/
30. int main(int argc,char * argv[])
31. {
33. //int list[]={5,3,4,9,1,7,11};
34. int list[]={15,5,16,3,12,20,10,13,18,23,6,7};
35. root = CreateBSTree(list,12);
36. std::cout<<"Cearte BSTree."<<std::endl;
37. //Print(root);
38. //std::cout<<Successor(FindNode(root,4))->node_value;
39. //Print(root);
40. //std::cout<<std::endl;
41. //DeleteTreeNode(root,15);
42. //Print(root);
43. Tree * t = FindNode(root,18);
44. std::cout<<PredeSuccessor(t)->node_value;
45. getchar();
46. return 0;
47. }
48. /*找出樹中的最小節點
49. p數的根節點
50. */
51. int Minimum(Tree * p)
52. {
53. Tree * t = TreeMinimum(p);
54. if(t != NULL)
55. {
56. return t->node_value ;
57. }
58. else
59. {
60. return -1;
61. }
62. }
63. Tree * TreeMinimum(Tree * p)
64. {
65. if(p->left == NULL)
66. {
67. return p;
68. }
69. TreeMinimum(p->left);
70. }
71. /*找出樹中的最大節點*/
72. int Maximum(Tree * p)
73. {
74. Tree * t = TreeMaximum(root);
75. if(t != NULL)
76. {
77. return t->node_value ;
78. }
79. else
80. {
81. return -1;
82. }
83. }
84. Tree * TreeMaximum(Tree * p)
85. {
86. if(p->right == NULL)
87. {
88. return p;
89. }
90. TreeMaximum(p->right);
91. }
92. /*假定所有的節點值都不相同，找到一個節點的指針
93. p樹的根節點，
94. node_value要查找的節點的值
95. */
96. Tree * FindNode(Tree * p,int node_value)
97. {
98. if(p == NULL)
99. {
100. return NULL;/*遞歸返回標志*/
101. }
102. if(p->node_value == node_value)
103. {
104. return p;
105. }
106. if(p->node_value < node_value)
107. {
108. FindNode(p->right, node_value);
109. }
110. else
111. {
112. FindNode(p->left, node_value);
113. }
115. }
116. /*找出一個節點的後繼結點*/
117. Tree * Successor(Tree * p)
118. {
119. if(p == NULL)
120. {
121. return NULL;
122. }
123. if(p->right != NULL)
124. {
125. return TreeMinimum(p->right);
126. }
127. Tree * t = p->parent ;
128. while((t != NULL) && (p == t->right))
129. {
130. p = t;
131. t = t->parent ;
132. }
133. return t;
134. }
135. /*找到一個節點的前驅節點
136. p為節點的指針
137. */
138. Tree * PredeSuccessor(Tree * p)
139. {
140. if(p == NULL)
141. {
142. return NULL;
143. }
144. else if(p->left != NULL)
145. {/*如果左子樹不為空，則前驅為其左子樹的最大值節點*/
146. return TreeMaximum(p->left);
147. }
148. else
149. {
150. Tree * t = p->parent ;
151. while((t != NULL) && (p == t->left))
152. {/*注意節點t的方向，這個與尋找後繼節點相反*/
153. p = t;
154. t = t->parent;
155. }
156. return t;
157. }
158. }
159. /*刪除一個節點
160. p為樹根節點指針
161. node_value要刪除的節點的值
162. */
163. bool DeleteTreeNode(Tree * p,int node_value)
164. {
165. Tree * t = FindNode(p,node_value);
166. if(t == NULL)
167. {
168. return false;
169. }
170. if((t->left == NULL)&&(t->right == NULL))
171. {/*沒有子節點*/
172. Tree* tmp = t;
173. if(tmp->parent->left == tmp)
174. {
175. tmp->parent->left = NULL;
176. }
177. else
178. {
179. tmp->parent->right = NULL;
180. }
181. delete tmp;
182. tmp = NULL;
183. }
184. else if((t->left == NULL)||(t->right == NULL))
185. {/*一個子節點*/
186. Tree* tmp = t;
187. if(tmp->parent->left == tmp)
188. {
189. tmp->parent->left = (tmp->left ==NULL)?tmp->right :tmp->left;
190. }
191. else
192. {
193. tmp->parent->right = (tmp->left ==NULL)?tmp->right :tmp->left;
194. }
195. delete tmp;
196. tmp = NULL;
197. }
198. else
199. {/*兩個子節點*/
200. Tree* s = Successor(t);
201. if(s == NULL)
202. {
203. return false;
204. }
205. t->node_value = s->node_value ;
206. DeleteTreeNode(s);
208. }
209. }
210. /*刪除一個節點
211. p為樹根節點指針
212. */
213. bool DeleteTreeNode(Tree * n)
214. {
215. if(n == NULL)
216. {
217. return NULL;
218. }
219. else if((n->left == NULL)&&(n->right == NULL))
220. {/*沒有子節點*/
221. Tree* tmp = n;
222. if(tmp->parent->left == tmp)
223. {
224. tmp->parent->left = NULL;
225. }
226. else
227. {
228. tmp->parent->right = NULL;
229. }
230. delete tmp;
231. tmp = NULL;
232. }
233. else if((n->left == NULL)||(n->right == NULL))
234. {/*一個子節點*/
235. Tree* tmp = n;
236. if(tmp->parent->left == tmp)
237. {
238. tmp->parent->left = (tmp->left ==NULL)?tmp->right :tmp->left;
239. }
240. else
241. {
242. tmp->parent->right = (tmp->left ==NULL)?tmp->right :tmp->left;
243. }
244. delete tmp;
245. tmp = NULL;
246. }
247. else
248. {/*兩個子節點*/
249. Tree* s = Successor(n);
250. if(s == NULL)
251. {
252. return false;
253. }
254. n->node_value = s->node_value ;
255. DeleteTreeNode(s);
257. }
258. }
259. /*生成二叉查找樹*/
260. Tree * CreateBSTree(int * array_list,int array_length)
261. {
262. if(array_length <= 0)
263. {
264. return false;
265. }
266. Tree * root = NULL;
267. root = new BSTree();
268. root->left = NULL;
269. root->right = NULL;
270. root->parent = NULL;
271. root->node_value = array_list[0];
272. for(int i=1;i<array_length;i++)
273. {
274. CreateBSTree(root,array_list[i]);
275. }
276. return root;
277. }
278. void CreateBSTree(Tree * root,int node_value)
279. {
280. if(root == NULL)
281. {
282. return ;
283. }
284. if(root->node_value > node_value)
285. {
286. if(root->left == NULL)
287. {
288. Tree * node = new Tree();
289. node->left = NULL;
290. node->right = NULL;
291. node->node_value = node_value;
292. node->parent = root;
293. root->left = node;
295. }
296. else
297. {
298. CreateBSTree(root->left,node_value);
299. }
300. }
301. else
302. {
303. if(root->right == NULL)
304. {
305. Tree * node = new Tree();
306. node->left = NULL;
307. node->right = NULL;
308. node->node_value = node_value;
309. node->parent = root;
310. root->right = node;
311. }
312. else
313. {
314. CreateBSTree(root->right,node_value);
315. }
316. }
317. }
318. /*中序排序輸出二叉查找樹*/
319. void Print(Tree* root)
320. {
321. if(root == NULL)
322. {
323. return ;
324. }
325. Print(root->left);
326. std::cout<<root->node_value<<"\t";
327. Print(root->right);
328. }