【算法导论】二叉查找树的操作C++实现

【算法导论】二叉查找树的操作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); 
16.  
17. void Print(Tree* root); 
18.  
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. { 
32.      
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.     } 
114.      
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); 
207.  
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); 
256.  
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; 
294.  
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. }