root/libbst/libbst.c

Revision 69, 4.2 KB (checked in by aqua, 4 years ago)

code clean up finished~
Line 
1#include <stdlib.h>
2
3#include "libbst.h"
4
5/* get the min value of tree.. */
6static int bst_get_min( bst_ptr node ){
7
8        /* go leftest!! */
9        if( node != NULL )
10                while( node->left != NULL )
11                        node = node->left;
12
13        return node->var;
14
15}
16
17/* get the max value of tree.. */
18static int bst_get_max( bst_ptr node ){
19
20        /* go rightest !! */
21        if( node != NULL )
22                while( node->right != NULL )
23                        node = node->right;
24
25        return node->var;
26
27}
28
29/* get level */
30int bst_get_level( bst_ptr root ){
31
32        int l_level, r_level;
33       
34        if( root == NULL )
35                return 0;
36
37        else{
38
39                /* get left child's level */
40                if( root->left != NULL )
41                        l_level = bst_get_level( root->left );
42
43                else
44                        l_level = 0;
45
46                /* get right child's level */
47                if( root->right != NULL )
48                        r_level = bst_get_level( root->right );
49
50                else
51                        r_level = 0;
52       
53               
54                /* left child's node is more than right's.. return l_level + 1 */
55                if( l_level > r_level )
56                        return ( 1 + l_level );
57               
58                else
59                        return ( 1 + r_level );
60
61        }
62
63}
64
65/* search */
66bst_ptr bst_search( bst_ptr root, int var ){
67
68        bst_ptr tmp;
69        tmp = root;
70       
71        while( tmp != NULL ){
72                       
73                /* searching complete.. */
74                if( tmp->var == var )
75                        return tmp;
76
77                /* go left */
78                else if( tmp->var > var )
79                        tmp = tmp->left;
80
81                /* go right */
82                else if( tmp->var < var )
83                        tmp = tmp->right;
84
85        }
86        return NULL;
87       
88}
89
90static bst_ptr bst_create_node( int var ){
91
92        bst_ptr tmp;
93
94        tmp = (bst_ptr) malloc( sizeof(bst) ); 
95       
96        tmp->var = var;
97        tmp->left = NULL;
98        tmp->right = NULL;
99
100        return tmp;
101
102}
103
104#if 0
105/* this interface will be better in avl tree */
106static bst_ptr bst_real_add( bst_ptr cur, int var ){
107
108        bst_ptr tmp;
109       
110        if( cur == NULL ){
111
112                tmp = bst_create_node( var );
113                return tmp;
114
115        }
116
117        /* if the key is already in this tree... then error! */
118        else if( cur->var == var )
119                return NULL;
120
121        /* if the given key is smaller than current key... traversal right child */
122        else if( cur->var < var ){
123
124                if( (tmp = bst_real_add( cur->right, var )) == NULL )
125                        return NULL;
126               
127                cur->right = tmp;
128                return cur;
129
130        }
131
132        /* if the given key is bigger than current key... traversal left child */
133        else {
134                if( (tmp = bst_real_add( cur->left, var )) == NULL )
135                        return NULL;
136
137                cur->left = tmp;
138                return cur;
139        }
140
141}
142#endif
143
144/* add */
145int bst_add( bst_ptr* root, int var ){
146
147        bst_ptr tmp;
148
149        /*
150         * simple way (this will be use in AVL)
151         *
152         * (*root) = bst_real_add( *root, var );
153         * return 1;
154         *
155         * simple way finished
156         */
157
158        /* if tree is empty, then create node & make it root node of tree */
159        if( (*root) == NULL ){
160                (*root) = bst_create_node( var );
161                return 1;
162        }
163
164        tmp = (*root);
165        do {
166
167                /* if given key is bigger than current key */
168                if( tmp->var > var ){
169
170                        /* follow left child, if exists */
171                        if( tmp->left != NULL )
172                                tmp = tmp->left;
173                       
174                        /* if not, create node & attach it as left child */
175                        else{
176                                tmp->left = bst_create_node( var );
177                                break;
178                        }
179                       
180                }
181
182                /* if given key is same as current key then error! */
183                else if( tmp->var == var )
184                        return ERROR;
185               
186                /* if given key is bigger than current key */
187                else {
188
189                        /* if this node has right child, then follow it */
190                        if( tmp->right != NULL )
191                                tmp = tmp->right;
192                       
193                        /* else create node and attach it as right child */
194                        else{
195                                tmp->right = bst_create_node( var );
196                                break;
197                        }
198
199                }
200
201        } while( tmp != NULL );
202
203        return 1;
204       
205}
206
207/* del */
208int bst_del( bst_ptr* root, int var ){
209
210        bst_ptr mother, cur;
211        int tmp;
212
213        mother = NULL;
214        cur = (*root);
215
216        /* find the node */
217        while( cur != NULL ){
218                /* searching complete.. */
219                if( cur->var == var )
220                        break;
221                /* go left */
222                else if( cur->var > var ){
223                        mother = cur;
224                        cur = cur->left;
225                }
226                /* go right */
227                else if( cur->var < var ){
228                        mother = cur;
229                        cur = cur->right;
230                }
231        }
232
233        /* if can't find given key, then error */
234        if( cur == NULL )
235                return ERROR;
236
237        /* if has left child */
238        else if( cur->left != NULL ){
239                tmp = bst_get_max(cur->left);
240                bst_del( &(cur->left), tmp );
241
242                cur->var = tmp;
243                return 1;
244        }
245        /* if has right child */
246        else if( cur->right != NULL ){
247                tmp = bst_get_min(cur->right);
248                bst_del( &(cur->right), tmp );
249
250                cur->var = tmp;
251                return 1;
252        }
253        /* if has no child */
254        else {
255                if( mother == NULL )
256                        (*root) = NULL;
257
258                else if( cur == mother->left )
259                        mother->left = NULL;
260
261                else 
262                        mother->right = NULL;
263
264                free(cur);
265                return 1;
266        }
267
268}
269
Note: See TracBrowser for help on using the browser.