Binary Search Tree Operations

Binary Search Tree Operations 

//Main File

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

//Header File

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