Binary Search Tree Operations(Program)

Binary Search Tree Operations

MAIN FILE:-

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include "tree.h"
4. 
   
5. NODE * create(NODE *root);
6. NODE * insert(NODE *root,int n);
7. NODE *search(NODE * root, int n);
8. void display();
9. void preorder(NODE * root);
10. void inorder(NODE * root);
11. void postorder(NODE * root);
12. NODE * deletebst(NODE *root, int n);
13. 
    
14. int Node_count(NODE *root);
15. int Leaf_count(NODE *root);
16. NODE *treecopy(NODE *root);
17. int comparebst(NODE *root, NODE *root1);
18. int sumOdd(NODE *node);
19. int sumEven(NODE *node1);
20. void mirror(NODE *root);
21. int smallest(NODE * root);
22. int largest(NODE * root);
23. 
    
24. void main()
25. {
26. NODE *root=NULL, *root1=NULL;
27.     int n, num, osum, esum, choice;
28. printf("\t\t>>Operations of Binary Search Tree<<\n\n");
29.     printf("\t\t\t>>First Create BST<<\n");
30.        
31.     //CREATE
32.     root = create(root);
33.     root1 = create(root1);
35. do
36. {
37. printf("\n\n1.INSERT");
38. printf("\n2.SEARCH");
39. printf("\n3.DISPLAY");
40. printf("\n4.PERODER");
41. printf("\n5.INODER");
42. printf("\n6.POSTODER");
43. printf("\n7.DELETE");
44. printf("\n8.COUNT OF TOTAL NODES");
45. printf("\n9.COUNT OF LEAF NODES");
46. printf("\n10.COPY BST");
47. printf("\n11.MIRROR OF BST");
48. printf("\n12.SUM OF ODD NUMBERS");
49. printf("\n13.SUM OF EVEN NUMBERS");
50. printf("\n14.COMPARE BST");
51. printf("\n15.SMALLEST NUMBER IN BST");
52. printf("\n16.LARGEST NUMBER IN BST");
53.         printf("\n17.Exit\n");
54. printf("\n Enter your Choice:\t");
55.         scanf("%d",&choice);
56.         
57. switch(choice)
58. {
59. case 1:  //INSERT
60. printf("\n\nEnter Element you want to insert:\t");
61.     scanf("%d",&n);
62. root = insert(root,n);
63. display(root);
64. break;
66. case 2: //SEARCH
67. printf("Enter Element to be search:\t");
68. scanf("%d", &n);
69. search(root, n);
70. break;
72. case 3: //DISPLAY
73. display(root);
74. break;
75. 
    
76. case 4:    //PREORDER
77. printf("\nPerorder traversal is:\t"); 
78.         preorder(root);
79. break;
80. 
    
81. case 5:  //INORDER
82. printf("\nInorder traversal is:\t");
83.         inorder(root);
84. break;
85. 
    
86. case 6: //POSTORDER
87. printf("\nPostorder traversal is:\t");
88.         postorder(root);
89. break;
90. 
    
91. case 7:  //DELETE
92. printf("\n\nEnter Element you want to delete:\t");
93.     scanf("%d",&n);
94. root = deletebst(root,n);
95. display(root);
96. break;
98. case 8:  //TOTAL NODE COUNT
99. num=Node_count(root);
100. printf("\nTotal Number of Nodes In BST:\t%d",num);
101. break;
103. case 9: //LEAF NODE
104. num=Leaf_count(root);
105. printf("\n Total Number of Leaf Nodes In BST:\t%d",num);
106. break;
108. case 10: //COPY BST
109. treecopy(root);
110. display(root);
111. break;
113. case 11: //MIRROR OF BST
114. mirror(root);
115. display(root);
116. break;
118. case 12: //SUM OF ODD NUMBERS
119. osum=sumOdd(root);
120. printf("\n Sum of odd numbers is :\t%d",osum);
121. break;
123. case 13: //SUM OF EVEN NUMBERS
124. esum=sumEven(root);
125. printf("\n Sum of even numbers is :\t%d",esum);
126. break;
128. case 14 : //COMPARE
129. if(comparebst(root, root1))
130. printf("\n\t>>BOTH TREE ARE EQUAL<<");
131. else
132. printf("\n\t>>BOTH TREE ARE NOT EQUAL<<");
133. break;
135. case 15: //SMALLEST ELEMENT IN BST
136. printf("\n\n\t >>Smallest element in BST is:\t %d", smallest(root));
137. break;
139. case 16: //LARGEST ELEMENT IN BST
140. printf("\n\t>>Largest element in BST is:\t %d", largest(root));
141. break;
144. case 17 : //EXIT
145. printf("\t\t>>BYE<<");
146. break;
148. default: printf("\t>>ENTER RIGHT CHOICE<<");
149.            
150. }
151. }while(choice!=17);
152. }

Header File:-

1.  typedef struct node
2.  {
3.     int info;
4.     struct node *left, *right;
5.  }NODE;
6. 
   
7. //CREATE
8.  NODE * create(NODE *root)
9.  {
10.     NODE *nn, *temp;
11.     int i, n, num;
12.     printf("\nHow many nodes you want to inserted...?\t ");
13.     scanf("%d",&n );
14.     for(i=1; i<=n; i++)
15.     {
16.     nn=(NODE*)malloc(sizeof(NODE));
17.     printf("Enter %d Element:\t",n);
18.     scanf("%d",&num);
19.     nn->info = num;
20.     nn->left=nn->right=NULL;
21.     if(root==NULL)
22.     root=nn;
23.     else
24.     {
25.     temp=root;
26.     while(1)
27.     {
28.     if(nn->info < temp->info)
29.     if(temp->left == NULL)
30.     {
31.     temp->left=nn;
32.     break;
33.     }
34.     else
35.     temp=temp->left;
36.     else
37.     if(temp->right == NULL)
38.     {
39.     temp->right=nn;
40.     break;
41.     }
42.     else
43.     temp=temp->right;
44.     }//while
45.     }//else
46.     }//for
47.     return(root);
48.  }
49.  
50. //DISPLAY
51. void display(NODE *root)
52. {
53. NODE *temp=root;
54. if(temp != NULL)
55. {
56. printf("\t%d",temp->info);
57. display(temp->left);
58. display(temp->right);
59. }
60. }
61. 
    
62. //INSERT 
63. NODE * insert(NODE *root, int n)
64. {
65.     NODE *temp, *nn;
66.     nn = (NODE*)malloc(sizeof(NODE));
67.     nn->left=nn->right=NULL;
68.     nn->info=n;
69. 
    
70.     if(root==NULL)
71.     {
72.     root=nn;
73.     return root;
74.     }
75.     else
76.     {
77.     temp=root;
78.     while(1)
79.     {
80.     if(n < temp->info)
81.     {
82.     if(temp->left==NULL)
83.     {
84.     temp->left=nn;
85.     break;
86.     }
87.     else
88.     temp=temp->left;
89.     }
90.     else
91.     if(n > temp->info)
92.     {
93.     if(temp->right==NULL)
94.     {
95.     temp->right=nn;
96.     break;
97.     }
98.     else
99.     temp=temp->right;
100.     }//if
101.     }//while
102.     }//else
103.     return(root);
104. }
105. 
     
106. //PERODER
107. void preorder(NODE * root)
108. {
109.     NODE *temp = root;
110.     if(temp != NULL)
111.     {
112. printf("%d\t", temp->info);
113.     preorder(temp->left);
114.     preorder(temp->right);
115. }
116. }
117. 
     
118. //INORDER
119. void inorder(NODE * root)
120. {
121.     NODE *temp = root;
122.     if(temp != NULL)
123.     {
124.     inorder(temp->left);
125.     printf("%d\t", temp->info);
126.     inorder(temp->right);
127.     }
128. }
129. 
     
130. //POSTORDER
131. void postorder(NODE * root)
132.  {
133.     NODE *temp = root;
134.     if(temp != NULL)
135.     {
136.     postorder(temp->left);
137.         postorder(temp->right);
138.         printf("%d\t", temp->info);
139.     }
140.  }
141. 
     
142.  //Delete 
143.  NODE * deletebst(NODE *root, int n)
144.  {
145.     NODE * temp = root;
146. NODE * prev = NULL;
148. while(temp != NULL && temp->info != n)
149. {
150. prev = temp;
151. if(n < temp->info)
152. temp = temp->left;
153. else
154. temp = temp->right;
155. }
157. if(temp==NULL)
158. {
159. printf("\t'%d' Not Found In BST\n",n);
160. return root;
161. }
163. if(temp->left == NULL || temp->right == NULL)
164. {
165. NODE *nn;
166. if(temp->left == NULL)
167. nn = temp->right;
168. else
169. nn = temp->left;
171. if(prev == NULL)
172. return nn;
174. if(temp == prev->left)
175. prev->left = nn;
176. else
177. prev->right = nn;
179. free(temp);
180. }
181. else
182. {
183. NODE * p = NULL;
184. NODE * temp1;
186. temp1 = temp->right;
187. while(temp1->left != NULL)
188. {
189. p = temp1;
190. temp1 = temp1->left;
191. }
192. if(p != NULL)
193. p->left = temp1->right;
194. else
195. temp->right = temp1->right;
197. temp->info = temp1->info;
198. free(temp1);
199. }
200. return root;
201. }
203.     
204. //Search
205. NODE *search(NODE * root, int n)
206. {
207. NODE *temp = root;
208. while(temp != NULL)
209. {
210. if(temp->info==n)
211. {
212. printf("\t'%d'  Is Present In BST", n);
213. return temp;
214. }
215. if(n < temp->info)
216. temp=temp->left;
217. else
218. temp=temp->right;
219. }
220. printf("\t>>'%d' IS Not Present In BST<<",n);
221. }
222. 
     
223. //Count Total Nodes
224. int Node_count(NODE *root)
225. {
226. static int count=0;
227. NODE  *temp=root;
228. if(temp != NULL)
229. {
230. count++;
231. Node_count(temp->left);
232. Node_count(temp->right);
233. }
234. return (count);
235. }
236. 
     
237. //Count Leaf Node
238. int Leaf_count(NODE *root)
239. {
240. static int count=0;
241. NODE *temp=root;
242. if(temp != NULL)
243. {
244. if(temp->left==NULL && temp->right==NULL)
245. count++;
246. Leaf_count(temp->left);
247. Leaf_count(temp->right);
248. }
249. return (count);
250. }
251. 
     
252. //COPY TREE
253. NODE *treecopy(NODE *root)
254. {
255. NODE *nn;
256. if(root != NULL)
257. {
258. nn=(NODE*)malloc(sizeof(NODE));
259. nn->info=root->info;
260. nn->left = treecopy(root->left);
261. nn->right = treecopy(root->right);
262. return (nn);
263. }
264. else
265. return NULL;
266. }
267. 
     
268. //MIRROR
269. void mirror(NODE *root)
270. {
271. NODE *temp;
272. if(root != NULL)
273. {
274. if(root->left)
275. mirror(root->left);
276. if(root->right)
277. mirror(root->left);
278. temp=root->left;
279. root->left = root->right;
280. root->right = temp;
281. }
282. }
283. 
     
284. 
     
285. //SUM OF ODD NUMBERS
286. int sumOdd(NODE *node)
287. {
288. int osum=0;
289. if(node != NULL)
290. {
291. if((node->info % 2 )!= 0)
292. osum += node->info;
293. osum += sumOdd(node->left);
294. osum += sumOdd(node->right);
295. }
296. return osum;
297. }
298. 
     
299. 
     
300. //SUM OF EVEN NUMBERS
301. int sumEven(NODE *node1)
302. {
303. int esum=0;
304. if(node1 != NULL)
305. {
306. if((node1->info % 2 )== 0)
307. esum += node1->info;
308. esum += sumEven(node1->left);
309. esum += sumEven(node1->right);
310. }
311. return esum;
312. }
313. 
     
314. 
     
315. //COMPARE
316. int comparebst(NODE *root, NODE *root1)
317. {
318. if(root==NULL && root1==NULL)
319. return 1;
320. if(root != NULL && root1 != NULL)
321. {
322. return
323. (
324. root->info == root1->info &&
325. comparebst(root->left, root1->left) &&
326. comparebst(root->right, root1->right)
327. );
328. }
329. return 0;
330. }
331. 
     
332. //SMALLEST
333. int smallest(NODE * root) 
334. {
335. NODE *temp = root;
336. while (temp->left != NULL) 
337. {
338. temp = temp->left;
339. }
340. return(temp->info);
341. }
342. 
     
343. //largest
344. int largest(NODE * root) 
345. {
346. NODE *temp = root;
347. while (temp->right != NULL) 
348. {
349. temp = temp->right;
350. }
351. return(temp->info);
352. }

                                           

                                                                                                                             //ThE ProFessoR