一个链式二叉搜索树接口（为下一篇红黑树的内容做铺垫）

  1 /*
  2  *2 binary search tree
  3  *data struct : list
  4  *
  5  */
  6 
  7 #include <stdio.h>
  8 #include <stdlib.h>
  9 
 10 #define VALUE_TYPE int
 11 
 12 typedef struct search_tree_node
 13 {
 14     VALUE_TYPE value;
 15     struct search_tree_node *l_child;
 16     struct search_tree_node *r_child;
 17 
 18 }search_tree_node,*search_tree;
 19 
 20 /*name: search_tree_init
 21  * *return:
 22  * search_tree 
 23  */
 24 
 25 search_tree search_tree_init()
 26 {
 27     return NULL;
 28 }
 29 
 30 /*
 31  * *name: search_tree_node_create
 32  * *return:
 33  * NULL failed else success
 34  */
 35 
 36 search_tree_node *search_tree_node_create(VALUE_TYPE value)
 37 {
 38     search_tree_node *node = (search_tree_node *)malloc(sizeof(search_tree_node));
 39 
 40     if(node == NULL)
 41     {
 42         return NULL;
 43     }
 44 
 45     node->l_child = NULL;
 46     node->r_child = NULL;
 47     node->value = value;
 48     
 49     return node;
 50 }
 51 
 52 /*
 53  * * name: search_tree_insert
 54  * * return:
 55  * 1 success -1 failed
 56  */
 57 
 58 int search_tree_insert(search_tree *root,VALUE_TYPE value)
 59 {
 60     if(root == NULL)
 61     {
 62         return -1;
 63     }
 64 
 65     search_tree_node **link = root; //to save the child node
 66     search_tree_node *current = NULL;
 67 
 68     while((current = *link) != NULL)
 69     {
 70         if(value == current->value)
 71         {
 72             return -1; //the value is already exist int the tree;
 73         }
 74         else
 75         {
 76             if(value < current->value)
 77             {
 78                 link = &(current->l_child);
 79             }
 80             else
 81             {
 82                 link = &(current->r_child);
 83             }
 84         }
 85     }
 86     
 87     *link = search_tree_node_create(value);
 88     
 89     return 1;
 90 }
 91 
 92 /*
 93  * *name: search_tree_find
 94  * *return:
 95  * 1 find -1 not find
 96  */
 97 
 98 int search_tree_find(search_tree root,VALUE_TYPE value)
 99 {
100     if(root == NULL)
101     {
102         return -1;
103     }
104 
105     search_tree_node *current = root;
106     
107     while(current != NULL)
108     {
109         if(value == current->value)
110         {
111             return 1;
112         }
113         else
114         {
115             if(value < current->value)
116             {
117                 current = current->l_child;
118             }
119             else
120             {
121                 current = current->r_child;
122             }
123         }
124     }
125 
126     return -1;
127 }
128 
129 /*
130  * *name: search_tree_delete
131  * *return:
132  * 1 delete ok -1 delete failed
133  */
134 
135 int search_tree_delete(search_tree root,VALUE_TYPE value)
136 {
137     if(root == NULL)
138     {
139         return -1;
140     }
141 
142     search_tree_node **link = &root;
143     search_tree_node *current = *link;
144         int flag = 0;    
145 
146     while((current = *link) != NULL)
147     {
148         if(value == current->value)
149         {
150             flag = 1;
151             break;
152         }
153         else
154         {
155             if(value < current->value)
156             {
157                 link = &(current->l_child);
158             }
159             else
160             {
161                 link = &(current->r_child);
162             }
163         }
164     }
165 
166     if(flag == 0)
167     {
168         return -1; //the node is not exist 
169     }
170     
171     if((*link)->l_child == NULL && (*link)->r_child == NULL)
172     {//the node is leaf node
173         free(*link);
174         *link = NULL;    
175 
176         return 1;    
177     }
178     
179     if((*link)->l_child != NULL && (*link)->r_child != NULL)
180     {//the node has two child
181         search_tree_node **link_sub = &((*link)->l_child);
182         //search_tree_node *current_sub = *link_sub;
183         
184         search_tree_node *parent = NULL;
185         while( ( (*link_sub)->r_child ) != NULL )
186         {//find the left sub tree biggest node
187             //link_sub = &(current_sub->r_child); //logic error, calculate a r_child node redundant
188             parent = *link_sub;
189             link_sub = &((*link_sub)->r_child);
190         }
191         
192         (*link)->value = (*link_sub)->value; //change current sub tree root node value to left sub tree biggest node value
193         
194         if(parent != root && *link_sub != root)
195         {
196             parent->r_child = link_sub->l_child; //change node
197         }
198         
199         free(*link_sub);
200         *link_sub = NULL;
201 
202         return 1;        
203     }    
204 
205     //the node just have one child
206     search_tree_node *current_child;
207     
208     if((*link)->l_child != NULL)
209     {//just have left child
210         current_child = (*link)->l_child;
211     }
212     else
213     {//just have right child 
214         current_child = (*link)->r_child;
215     }    
216 
217     free(*link);
218     *link = current_child;
219     
220     return 1;
221 
222 }
223 
224 
225 /*
226  * *name:pre_order_tree
227  */
228 
229 void pre_order_tree(search_tree root,void (*search_tree_callback)(VALUE_TYPE value))
230 {
231     if(root != NULL)
232     {
233         search_tree_callback(root->value);
234         pre_order_tree(root->l_child,search_tree_callback);
235         pre_order_tree(root->r_child,search_tree_callback);
236     }
237 }
238 
239 /*
240  * *name:post_order_tree
241  */
242 
243 void post_order_tree(search_tree root,void (*search_tree_callback)(search_tree_node *current))
244 {
245     if(root != NULL)
246     {
247         post_order_tree(root->l_child,search_tree_callback);
248         post_order_tree(root->r_child,search_tree_callback);
249         search_tree_callback(root);
250     }
251 }
252 
253 /*
254  *name:print_node
255  */
256 
257 static void tree_node_print(VALUE_TYPE value)
258 {
259     printf("%d ",value);
260 }
261 
262 
263 /*
264  *name:free_node
265  */
266 
267 static void tree_node_free(search_tree_node *current)
268 {
269     free(current);
270 }
271 
272 /*
273  * *name:search_tree_destroy
274  */
275 
276 void search_tree_destroy(search_tree *root)
277 {//use post traverse to free tree node
278     if(root == NULL)
279     {
280         return;
281     }
282 
283     search_tree_node *current = *root;
284     
285     post_order_tree(current,tree_node_free);
286 
287     *root = NULL;
288 }
289 
290 int main()
291 {
292     search_tree tree = search_tree_init();
293     
294     int i = 0;
295     int value;
296     
297     for(i = 0; i < 10; i++)
298     {
299         scanf("%d",&value);
300         
301         search_tree_insert(&tree,value);
302     }    
303 
304     pre_order_tree(tree,tree_node_print);
305     printf("
");
306 
307     scanf("%d",&value);
308     search_tree_delete(tree,value);
309     pre_order_tree(tree,tree_node_print);
310     printf("
");
311     
312     scanf("%d",&value);
313     search_tree_delete(tree,value);
314     pre_order_tree(tree,tree_node_print);
315     printf("
");
316     
317     scanf("%d",&value);
318     search_tree_delete(tree,value);
319     pre_order_tree(tree,tree_node_print);
320     printf("
");
321 
322     search_tree_destroy(&tree);
323     pre_order_tree(tree,tree_node_print);
324 
325 }