Tree Traversal

1:  #include<stdio.h>  
2:  #include<conio.h>  
3:  #include<alloc.h>  
4:  struct bnode  
5:  {  
6:   int data;  
7:   struct bnode *left;  
8:   struct bnode *right;  
9:  }*start;  
10:  typedef struct bnode b;  
11:  struct bnode *binsearch(struct bnode *,int);  
12:  struct bnode *findmin(struct bnode *);  
13:  struct bnode *delete(struct bnode *,int);  
14:  void main()    
15:  {  
16:   int n,chk,choice,chk1;  
17:   start = NULL;  
18:   clrscr();  
19:   do  
20:   {  
21:    printf("\n\n\t\t\tMENU");  
22:    printf("\n\t\t\t*******");  
23:    printf("\n\n\t\t\t1. Adding new node.");  
24:    printf("\n\n\t\t\t2. Traversing tree");  
25:    printf("\n\n\t\t\t3. Searching");  
26:    printf("\n\n\t\t\t4. Deletion");  
27:    printf("\n\n\t\t\t5. Exit");  
28:    printf("\n\n\t\t\t Enter ur choice");  
29:    scanf("%d",&n);  
30:    if(n == 1)  
31:    {  
32:     add();  
33:    }  
34:    if(n == 3)  
35:    {  
36:     struct bnode *src;  
37:     printf("\n\t\t\tEnter the value to be searched: ");  
38:     scanf("%d",&chk);  
39:     src = binsearch(start,chk);  
40:     if(src != NULL)  
41:       printf("\n\t\t\tThe searched node is %d",src->data);  
42:     else  
43:       printf("\n The node does not exist");  
44:    }  
45:    if(n == 2)  
46:    {  
47:     printf("\n\t\t\tBinary search traversal");  
48:     printf("\n\t\t\t***********************");  
49:     printf("\n\n\t\t\t1. Inorder");  
50:     printf("\n\n\t\t\t2. Preorder");  
51:     printf("\n\n\t\t\t3. Postorder");  
52:     printf("\n\n\t\t\tEnter choice for traversal");  
53:     scanf("%d",&choice);  
54:     if(choice == 1)  
55:       travinorder(start);  
56:     if(choice == 2)  
57:       travpreorder(start);  
58:     if(choice == 3)  
59:       travpostorder(start);  
60:    }  
61:    if(n == 4)  
62:    {  
63:     printf("\n\t\t\tEnter the value to be deleted");  
64:     scanf("%d",&chk1);  
65:     delete(start,chk1);  
66:    }  
67:   }while(n < 5);  
68:  getch();  
69:  }   
70:  /*Function to create a new node*/  
71:  struct bnode *getdata()  
72:  {  
73:   struct bnode *new1,*chek;  
74:   int t;  
75:   new1 = (b *)malloc(sizeof(b));  
76:   printf("\n\t\t\tEnter the number");  
77:   scanf("%d",&new1->data);  
78:   chek = binsearch(start,new1->data);  
79:   if(chek->data == new1->data)  
80:   {  
81:    printf("\n Already exist");  
82:    return NULL;  
83:   }  
84:   new1->left = NULL;  
85:   new1->right = NULL;  
86:   return new1;  
87:  }  
88:  /*function to add new nodes*/  
89:  add()  
90:  {  
91:   struct bnode *ptr,*prev,*x,*root;  
92:   x = getdata();  
93:   if(start == NULL)  
94:   {  
95:    start = x;  
96:    x->left = NULL;  
97:    x->right = NULL;  
98:   }  
99:   else  
100:   {  
101:    buildtree(start,x);  
102:   }  
103:   return;  
104:  }  
105:  buildtree(struct bnode *node,struct bnode *x)  
106:  {  
107:   if(x->data >node->data)  
108:   {  
109:    if(node->right == NULL)  
110:    {  
111:     printf("\n\t The added node is %d's right",node->data);  
112:     node->right = x;  
113:     x->left = NULL;  
114:     x->right = NULL;  
115:    }  
116:    else  
117:     buildtree(node->right,x);  
118:   }  
119:   else  
120:   {  
121:    if(x->data < node->data)  
122:    {  
123:     if(node->left == NULL)  
124:     {  
125:       printf("\n\t The added node is %d's left",node->data);  
126:       node->left = x;  
127:       x->left = NULL;  
128:       x->right = NULL;  
129:     }  
130:     else  
131:       buildtree(node->left,x);  
132:    }  
133:   }  
134:   return;  
135:  }  
136:  /*Function to search in the binary search tree*/  
137:  struct bnode *binsearch(struct bnode *node,int chk)  
138:  {  
139:   if(node != NULL)  
140:   {  
141:    if(node->data == chk)  
142:    {  
143:     printf("\n\t Node found in the tree");  
144:     return node;  
145:    }  
146:    else  
147:     if(chk < node->data)  
148:      binsearch(node->left,chk);  
149:    else  
150:      binsearch(node->right,chk);  
151:   }  
152:   else  
153:   {  
154:    printf("\n\t Node not found in the tree");  
155:    return NULL;  
156:   }  
157:  }  
158:  travinorder(struct bnode *node)  
159:  {  
160:   if(node!= NULL)  
161:   {  
162:    travinorder(node->left);  
163:    printf("\n%d",node->data);  
164:    travinorder(node->right);  
165:   }  
166:   return;  
167:  }  
168:  travpreorder(struct bnode *node)  
169:  {  
170:   if(node != NULL)  
171:   {  
172:    printf("\n%d",node->data);  
173:    travpreorder(node->left);  
174:    travpreorder(node->right);  
175:   }  
176:   return;  
177:  }  
178:  travpostorder(struct bnode *node)  
179:  {  
180:   if(node != NULL)  
181:   {  
182:    travpostorder(node->left);  
183:    travpostorder(node->right);  
184:    printf("\n%d",node->data);  
185:   }  
186:   return;  
187:  }  
188:  struct bnode *delete(struct bnode *fnd,int chk)  
189:  {  
190:   struct bnode *tmp;  
191:   if(fnd == NULL)  
192:     printf("\n Cant be deleted");\  
193:   else  
194:    if(chk < fnd->data)  
195:      fnd->left = delete(fnd->left,chk);  
196:   else  
197:    if(chk > fnd->data)  
198:      fnd->right = delete(fnd->right,chk);  
199:   else  
200:    if(fnd->left && fnd->right)  
201:    {  
202:     tmp = findmin(fnd->right);  
203:     fnd->data = tmp->data;  
204:     fnd->right = delete(fnd->right,tmp->data);  
205:    }  
206:   else  
207:   {  
208:    tmp = fnd;  
209:    if(fnd->left == NULL)  
210:     fnd = fnd->right;  
211:    else if(fnd->right == NULL)  
212:     fnd = fnd->left;  
213:    printf("\n Successfully deleted");  
214:   }  
215:   return fnd;  
216:  }  
217:  struct bnode *findmin(struct bnode *fnd)  
218:  {  
219:   if(fnd == NULL)  
220:    return NULL;  
221:   else  
222:    if(fnd->left == NULL)  
223:     return fnd;  
224:   else  
225:    return findmin(fnd->left);  
226:  }