0x01数据结构——C语言实现（二叉查找树）

二叉查找树是一种特殊的二叉树，使二叉树成为二叉查找树的性质是：对于树中的每一个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。这意味着，该树所有的元素可以用某种统一的方式排序。

二叉查找树的C语言实现：

b_search_tree.h

 1 #ifndef B_SEARCH_TREE_H
 2 #define B_SEARCH_TREE_H
 3 /*
 4 二叉树的节点用左右孩子表示法来存储。
 5 */
 6 
 7 typedef enum {
 8     false = 0,
 9     true
10 } BOOL;
11 
12 struct node;
13 typedef struct node node;
14 typedef node *Bstree;
15 typedef node *pos;
16 
17 //根据先序遍历数组来创建树（先序遍历数组中用'#'来表示空节点）
18 Bstree create_Bstree_preorder(int v[], int begin, int end);
19 Bstree create_Bstree(int v[], int *begin, int end);
20 
21 //将一颗树置空
22 Bstree make_empty(Bstree T);
23 
24 //判断树是不是空的
25 BOOL is_empty(Bstree T);
26 
27 //为节点p添加孩子节点x
28 BOOL add_child(node *p, int x);
29 
30 //先序遍历树
31 void preorder_traversal(Bstree T);
32 //以数组形式打印
33 //数组规定如下：用'#'来表示空节点
34 void preorder_traversal1(Bstree T);
35 
36 //中序遍历
37 void inorder_traversal(Bstree T);
38 
39 //后序遍历
40 void postorder_traversal(Bstree T);
41 
42 //寻找节点x的位置
43 pos search(int x, Bstree T);
44 
45 //寻找最大的节点
46 pos find_max(Bstree T);
47 
48 //寻找最小的节点
49 pos find_min(Bstree T);
50 
51 //插入节点x
52 Bstree insert_node(int x, Bstree T);
53 
54 //删除节点x
55 Bstree delete_node(int x, Bstree T);
56 pos find_rmin(Bstree T);
57 
58 //输出二叉树的高度
59 int Bstree_height(Bstree T);
60 
61 //输出二叉树总结点数目
62 int node_sum(Bstree T);
63 
64 //叶子结点数目
65 int leaves_sum(Bstree T);
66 
67 //取出节点p的值
68 int retrieve_p(pos p);
69 
70 //以层次方式打印输出
71 void print_Bstree(Bstree T);
72 void output(Bstree T, int i);
73 
74 
75 
76 #endif

b_search_tree.c

  1 #include "b_search_tree.h"
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <string.h>
  5 
  6 
  7 struct node {
  8     int val;
  9     struct node *left;//left child
 10     struct node *right;//right child
 11 };
 12 
 13 struct node;
 14 typedef struct node node;
 15 typedef node *Bstree;
 16 typedef node *pos;
 17 
 18 //根据先序遍历数组来创建树（先序遍历数组中用'#'来表示空节点）
 19 Bstree create_Bstree_preorder(int v[], int begin, int end)
 20 {
 21     return create_Bstree(v, &begin, end);
 22 }
 23 
 24 Bstree create_Bstree(int v[], int *begin, int end)
 25 {
 26     if((*begin)>end || v==NULL) 
 27         return NULL;
 28     Bstree T = NULL;
 29     if(v[*begin]!='#') {
 30         T=(node *)malloc(sizeof(node));
 31         T->val = v[*begin];
 32         (*begin)++;
 33         if(v[*begin] == '#') {
 34             T->left = NULL;
 35             (*begin)++;
 36             T->right = create_Bstree(v, begin, end);
 37         } else {
 38             T->left = create_Bstree(v, begin, end);
 39             (*begin)++;
 40             T->right = create_Bstree(v, begin, end);
 41         }
 42     }
 43     return T;
 44 }
 45 
 46 //将一颗树置空
 47 Bstree make_empty(Bstree T)
 48 {
 49     if(T!=NULL) {
 50         make_empty(T->left);
 51         make_empty(T->right);
 52         printf("free node with value %d
", T->val);
 53         free(T);
 54         T = NULL;
 55     }
 56     return T;
 57 }
 58 
 59 //判断树是不是空的
 60 BOOL is_empty(Bstree T)
 61 {
 62     return (T == NULL);
 63 }
 64 
 65 //为节点p添加孩子节点x
 66 BOOL add_child(node *p, int x)
 67 {
 68     if(p->left == NULL) {
 69         p->left = (node*)malloc(sizeof(node));
 70         p->left->val = x;
 71         p->left->left = p->left->right = NULL;
 72         return true;
 73     } else if(p->right == NULL) {
 74         p->right = (node*)malloc(sizeof(node));
 75         p->right->val = x;
 76         p->right->left = p->right->right = NULL;
 77         return true;
 78     } else {
 79         return false;
 80     }
 81 }
 82 
 83 //先序遍历树
 84 void preorder_traversal(Bstree T)
 85 {
 86     if(T!=NULL) {
 87         printf("%d", T->val);
 88         preorder_traversal(T->left);
 89         preorder_traversal(T->right);
 90     }
 91 }
 92 
 93 //以先序遍历数组形式打印
 94 //数组规定如下：用'#'来表示空节点
 95 void preorder_traversal1(Bstree T)
 96 {
 97     if(T!=NULL) {
 98         printf("%d", T->val);
 99         if(T->left == NULL) {
100             printf("#");
101             if(T->right == NULL) {
102                 printf("#");
103             } else {
104                 preorder_traversal1(T->right);
105             }
106         } else {
107             preorder_traversal1(T->left);
108             if(T->right == NULL) {
109                 printf("#");
110             } else {
111                 preorder_traversal1(T->right);
112             }
113         }
114     }
115 }
116 
117 //中序遍历
118 void inorder_traversal(Bstree T)
119 {
120     if(T!=NULL) {
121         inorder_traversal(T->left);
122         printf("%d", T->val);
123         inorder_traversal(T->right);
124     }
125 }
126 
127 //后序遍历
128 void postorder_traversal(Bstree T)
129 {
130     if(T!=NULL) {
131         postorder_traversal(T->left);
132         postorder_traversal(T->right);
133         printf("%d", T->val);
134     }
135 }
136 
137 //寻找节点x的位置
138 pos search(int x, Bstree T)
139 {
140     if(T!=NULL) {
141         if(T->val == x) {
142             return T;
143         } else if(x<T->val) {
144             return search(x, T->left);
145         } else {
146             return search(x, T->right);
147         }
148     } else {
149         return NULL;
150     }
151 }
152 
153 //寻找最大的节点
154 pos find_max(Bstree T)
155 {
156     if(T!=NULL) {
157         while(T->right!=NULL) {
158             T = T->right;
159         }
160     }
161     return T;
162 }
163 
164 //寻找最小的节点
165 pos find_min(Bstree T)
166 {
167     if(T != NULL) {
168         while(T->left != NULL) {
169             T = T->left;
170         }
171     }
172     return T;
173 }
174 
175 //插入节点x
176 Bstree insert_node(int x, Bstree T)
177 {
178     if(T == NULL) {
179         T = (node *)malloc(sizeof(node));
180         T->val = x;
181         T->left = T->right = NULL;
182     } else {
183         if(x>T->val) {
184             T->right = insert_node(x, T->right);
185         } else if(x<T->val) {
186             T->left = insert_node(x, T->left);
187         }
188     }
189     return T;
190 }
191 
192 //删除节点x
193 Bstree delete_node(int x, Bstree T)
194 {
195     /* 对于删除节点，需要考虑集中情况
196      * 如果节点是叶子节点，那么它可以被立即删除
197      * 如果节点有一个孩子，则该节点可以在其父节点调整指针跳过该节点后被删除
198      * 如果节点有两个孩子，一般的删除策略是用其右子树的最小的数据代替该节点的数据并递归地删除
199      * 那个节点。
200     */
201     if(T!=NULL) {
202         if(x<T->val) {
203             T->left = delete_node(x,T->left);
204         } else if(x>T->val) {
205             T->right = delete_node(x,T->right);
206         } else {
207             if(T->left!=NULL && T->right!=NULL) {
208                 /*两个孩子的节点*/
209                 /*寻找右子树最小节点*/
210 
211                 /*递归方式*/
212                 pos tmp = find_min(T->right);
213                 T->val = tmp->val;
214                 T->right = delete_node(T->val, T->right);
215 
216                 /*非递归方式*/
217 //              pos tmp = find_rmin(T);
218 //              if(tmp == T) {
219 //                  T->val = tmp->right->val;
220 //                  tmp->right = tmp->right->right;
221 //                  free(tmp->right);
222 //              } else {
223 //                  T->val = tmp->left->val;
224 //                  free(tmp->left);
225 //                  tmp->left = tmp->left->right;
226 //              }
227             } else {
228                 pos tmp = T;
229                 if(T->left == NULL) {
230                     T = T->right;
231                 } else if(T->right == NULL) {
232                     T = T->left;
233                 }
234                 free(tmp);
235             }
236         }
237     }
238     return T;
239 }
240 
241 pos find_rmin(Bstree T)
242 {
243     /*
244      * 寻找数T右子树最小节点
245      * 返回其父节点
246      */
247     if(T != NULL) {
248         pos tmp = T;
249         T = T->right;
250         while(T!=NULL && T->left!=NULL) {
251             tmp = T;
252             T = T->left;
253         }
254         return tmp;
255     } else {
256         return T;
257     }
258 }
259 
260 //输出二叉树中某个节点的高度
261 //对任意节点n_i，n_i的深度（depth）为从根到n_i的唯一路径的长。因此，根的深度为0。
262 //n_i的高（height）是从n_i到一片树叶的最长路径的长。
263 //因此所有树叶的高度都是0。一棵树的高等于它的根的高。
264 //一棵树的深度等于它的最深的树叶的深度，该深度总是等于这棵树的高。
265 int Bstree_height(Bstree T)
266 {
267     if(T!=NULL) {
268         int h;
269         if(T->left==NULL && T->right==NULL) {
270             h=0;
271         }else {
272             int h1, h2;
273             h1 = Bstree_height(T->left)+1;
274             h2 = Bstree_height(T->right)+1;
275             h = (h1>h2?h1:h2);
276         }
277         return h;
278     } else {
279         return -1;
280     }
281 }
282 
283 //输出二叉树总结点数目
284 int node_sum(Bstree T)
285 {
286 
287     if(T!=NULL) {
288         int sum = 0;
289         if(T->left==NULL && T->right==NULL) {
290             sum = 1;
291         }else {
292             int sum1, sum2;
293             sum1 = node_sum(T->left);
294             sum2 = node_sum(T->right);
295             sum = sum1+sum2+1;
296         }
297         return sum;
298     } else {
299         return 0;
300     }
301 
302 }
303 
304 //叶子结点数目
305 int leaves_sum(Bstree T)
306 {
307     int sum = 0;
308     if(T!=NULL) {
309         if(T->left==NULL && T->right==NULL) {
310             sum = 1;
311         }else {
312             int sum1, sum2;
313             sum1 = leaves_sum(T->left);
314             sum2 = leaves_sum(T->right);
315             sum = sum1+sum2;
316         }
317     }
318     return sum;
319 }
320 
321 //取出节点p的值
322 int retrieve_p(pos p)
323 {
324     return p->val;
325 }
326 
327 //以层次方式打印输出
328 void print_Bstree(Bstree T)
329 {
330     output(T,0);
331 }
332 void output(Bstree T, int i)
333 {
334     if(T != NULL) {
335         for(int j = 0; j<i; j++) {
336             printf("	");
337         }
338         printf("%d
", T->val);
339         i++;
340         if(!(T->left == NULL && T->right == NULL)) {
341             if(T->left == NULL) {
342                 printf("
");
343                 output(T->right,i);//输出右子树
344             } else if(T->right == NULL) {
345                 output(T->left,i);//输出左子树
346                 printf("
");
347             } else {
348                 output(T->left,i);//输出左子树
349                 output(T->right,i);//输出右子树
350             }
351         }
352     }
353 }

main.c

 1 #include "b_search_tree.h"
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 
 6 
 7 int main()
 8 {
 9     int A[13]={6,2,1,'#','#',4,3,'#','#','#',8,'#','#'};
10     int h = 0, sum = 0, leaves = 0;
11     Bstree T = create_Bstree_preorder(A,0,12);
12     int x = 6;
13     pos tmp = NULL;
14 
15     print_Bstree(T);
16     preorder_traversal(T);
17     printf("
");
18     inorder_traversal(T);
19     printf("
");
20     postorder_traversal(T);
21     printf("
");
22     preorder_traversal1(T);
23     printf("
");
24 
25     tmp = search(x,T);
26     printf("%d
", retrieve_p(tmp));
27     h = Bstree_height(tmp);
28     printf("height of the node %d: %d
", x,h);
29     tmp = find_max(T);
30     printf("the max node: %d
", retrieve_p(tmp));  
31     tmp = find_min(T);
32     printf("the min node: %d
", retrieve_p(tmp));
33 
34     sum = node_sum(T);
35     printf("this tree has %d node(s)
", sum);
36 
37     leaves = leaves_sum(T);
38     printf("this tree has %d leaves
", leaves);
39 
40     T = insert_node(5, T);
41     printf("after insert
");
42     print_Bstree(T);
43 
44     printf("after delete
");
45     T = delete_node(2, T);
46     print_Bstree(T);
47 
48     T = make_empty(T);
49     printf("empty? %d
", is_empty(T));
50     return 0;
51 }