Tree Insertion, Traversing , deletion and searching

1:  /**************************  
2:  * Headers includes  
3:  ***************************/  
4:  #include <stdio.h>  
5:  #include <stdlib.h>  
6:  /**************************  
7:  * Structure for tree  
8:   ***************************/  
9:  typedef struct node_  
10:  {  
11:    struct node_ *right;  
12:    struct node_ *left;  
13:    int i;  
14:  }node_t;  
15:  /**************************  
16:  * Global tree root  
17:  ***************************/  
18:  node_t *root = NULL;  
19:  /**************************  
20:  * Preorder tree display  
21:  ***************************/  
22:  void preorder(node_t *node)  
23:  {  
24:    if ( node == NULL)  
25:    {  
26:      return;  
27:    }  
28:    printf("%d\t",node->i);  
29:    preorder(node->left);  
30:    preorder(node->right);  
31:  }  
32:  /**************************  
33:  * Inorder tree display  
34:  ***************************/  
35:  void inorder(node_t *node)  
36:  {  
37:    if ( node == NULL)  
38:    {  
39:      return;  
40:    }  
41:    inorder(node->left);  
42:    printf("%d\t",node->i);  
43:    inorder(node->right);  
44:  }  
45:  /**************************  
46:  * Postorder tree display  
47:  ***************************/  
48:  void postorder(node_t *node)  
49:  {  
50:    if ( node == NULL)  
51:    {  
52:      return;  
53:    }  
54:    postorder(node->left);  
55:    postorder(node->right);  
56:    printf("%d\t",node->i);  
57:  }  
58:  /**************************  
59:  * Options for tree traversing  
60:  ***************************/  
61:  void display_tree()  
62:  {  
63:    int choice = 0;  
64:    printf("1.Preorder\n2.Inorder\n3.Postorder\nEnter choice or 0:");  
65:    scanf("%d",&choice);  
66:    switch(choice)  
67:    {  
68:      case 1:  
69:        preorder(root);  
70:        break;  
71:      case 2:  
72:        inorder(root);  
73:        break;  
74:      case 3:  
75:        postorder(root);  
76:        break;  
77:      default:  
78:        printf("wrong Choice\n");  
79:    }  
80:  }  
81:  /**************************  
82:  * Function to Insert data into tree  
83:  ***************************/  
84:  node_t *add_node(node_t *node,int data)  
85:  {  
86:    if( NULL == node )  
87:    {  
88:      node_t *node = (node_t *) malloc(sizeof(node_t));  
89:      node->left = NULL;  
90:      node->right = NULL;  
91:      node->i = data;  
92:      if ( NULL == root )  
93:      {  
94:        root = node;  
95:      }  
96:      return node;  
97:    } else {  
98:      if ( data > node->i)  
99:      {  
100:        node->right = add_node(node->right,data);  
101:      } else if ( data < node->i)  
102:      {  
103:        node->left = add_node(node->left,data);  
104:      }  
105:    }  
106:  }  
107:  /**************************  
108:  * Option to Insert data  
109:  ***************************/  
110:  void make_tree()  
111:  {  
112:    int data = 0;  
113:    do {  
114:      printf("Enter Data or '0' to Exit:");  
115:      scanf("%d",&data);  
116:      if ( data != 0 )  
117:      {  
118:        add_node(root,data);  
119:      }  
120:    }while(data != 0);  
121:  }  
122:  /**************************  
123:  * Delete Tree nodes  
124:  ***************************/  
125:  node_t *delete_tree(node_t *node,int data)  
126:  {  
127:    static node_t *cur = NULL;  
128:    node_t *temp1 = NULL,*temp2 = NULL;  
129:    if ( NULL == root )  
130:    {  
131:      printf("Tree is empty\n");  
132:      return NULL;  
133:    }  
134:    if ( NULL == node)  
135:    {  
136:      printf("Data %d Not found for delete\n",data);  
137:      return root;  
138:    }  
139:    /**  
140:     * Deleting root node  
141:     */  
142:    if ( data == root->i)  
143:    {  
144:      /*  
145:       * No chiled in root  
146:       */  
147:      if ( NULL == root->left && NULL == root->right)  
148:      {  
149:        free(root);  
150:        root = NULL;  
151:        return NULL;  
152:      }  
153:      /*  
154:       * Only right chiled in root  
155:       */  
156:      if ( NULL == root->left && NULL != root->right)  
157:      {  
158:        temp1 = root;  
159:        root = root->right;  
160:        temp1->right = NULL;  
161:        free(temp1);  
162:        temp1 = NULL;  
163:        return root;  
164:      }  
165:      /*  
166:       * Only Left chiled in root  
167:       */  
168:      if ( NULL != root->left && NULL == root->right)  
169:      {  
170:        temp1 = root;  
171:        root = root->left;  
172:        temp1->left = NULL;  
173:        free(temp1);  
174:        temp1 = NULL;  
175:        return root;  
176:      }  
177:      /*  
178:       * Both left and right child present in root  
179:       */  
180:      if ( NULL != root->left && NULL != root->right )  
181:      {  
182:        temp2 = root;  
183:        temp1 = root->right;  
184:        while(temp1->left != NULL)  
185:        {  
186:          cur = temp1;  
187:          temp1 = temp1->left;  
188:        }  
189:        if ( NULL == cur)  
190:        {  
191:          temp1->left = temp2->left;  
192:          root = temp1;  
193:          temp2->left = temp2->right = NULL;  
194:          free(temp2);  
195:          temp2 = NULL;  
196:          return root;  
197:        } else {  
198:          cur->left = temp1->right;  
199:          temp1->left = temp2->left;  
200:          temp1->right = temp2->right;  
201:          root = temp1;  
202:          temp2->left = temp2->right = NULL;  
203:          free(temp2);  
204:          temp2 = NULL;  
205:          return root;  
206:        }  
207:      }  
208:    }  
209:    /**  
210:     * Deleting any data from tree except root  
211:     */  
212:    if ( data > node->i)  
213:    {  
214:      cur = node;  
215:      delete_tree(node->right,data);  
216:    } else if ( data < node->i )  
217:    {  
218:      cur = node;  
219:      delete_tree(node->left,data);  
220:    } else if ( data == node->i)  
221:    {  
222:      /*  
223:       * Data found now delete the node  
224:       */  
225:      if ( node->left == NULL && node->right == NULL && cur == node)  
226:      {  
227:        free(node);  
228:        node = NULL;  
229:        return NULL;  
230:      }  
231:      if ( cur->i < node->i)  
232:      {  
233:        temp1 = node->left;  
234:        if ( NULL != temp1)  
235:        {  
236:          cur->right = node->left;  
237:          while(temp1->right != NULL)  
238:          {  
239:            temp1 = temp1->right;  
240:          }  
241:          temp1->right = node->right;  
242:        } else {  
243:          cur->right = node->right;  
244:        }  
245:      }  
246:      if ( cur->i > node->i)  
247:      {  
248:        temp1 = node->right;  
249:        if ( NULL != temp1)  
250:        {  
251:          cur->left = node->right;  
252:          while(temp1->left != NULL)  
253:          {  
254:            temp1 = temp1->left;  
255:          }  
256:          temp1->left = node->left;  
257:        } else {  
258:          cur->left = node->left;  
259:        }  
260:      }  
261:      node->left = node->right = NULL;  
262:      free(node);  
263:      node = NULL;  
264:    }  
265:    return root;  
266:  }  
267:  /**************************  
268:  * Search function  
269:  ***************************/  
270:  node_t *search_tree(int data)  
271:  {  
272:    node_t *temp = root;  
273:    while(temp != NULL && temp->i != data )  
274:    {  
275:      temp = (data > temp->i) ? temp->right : temp->left;  
276:    }  
277:    if ( NULL == temp)  
278:      return NULL;  
279:    return temp;  
280:  }  
281:  /**************************  
282:  * Main function to display tree options  
283:  ***************************/  
284:  main()  
285:  {  
286:    int choice = 0,data = 0;  
287:    node_t *node = NULL;  
288:    do {  
289:      printf("\n************* Tree ************\n1.Add\n2.Display\n3.Delete\n4.Search\nEnter Your Choice or Zero to exit:");  
290:      scanf("%d",&choice);  
291:      switch(choice)  
292:      {  
293:        case 1:  
294:          make_tree();  
295:          break;  
296:        case 2:  
297:          display_tree();  
298:          break;  
299:        case 3:  
300:          printf("Enter Data to delete:");  
301:          scanf("%d",&data);  
302:          root = delete_tree(root,data);  
303:          break;  
304:        case 4:  
305:          printf("Enter Data to Search:");  
306:          scanf("%d",&data);  
307:          node = search_tree(data);  
308:          if ( NULL == node)  
309:            printf("Data Not fount\n");  
310:          else  
311:            printf("Data Found :: %d\n",node->i);  
312:          break;  
313:        default:  
314:          printf("Wrong Choice\n");  
315:      }  
316:    }while(choice != 0);  
317:  }