DS | Practical - 11 | C Program to Implement Tree Traversals Inorder, Preorder and Postorder

 

Write a C Program to Implement Tree Traversals Inorder, Preorder and Postorder

GTU DS Practical-11

Implement recursive and non-recursive tree traversing methods in-order, preorder and post-order traversal in C.

Code for Tree Traversals

1. #include<stdio.h>
2. #include<malloc.h>
3. #include<stdlib.h>
4. struct node
5. {
6. int data;
7. struct node *lptr,*rptr;
8. };
10. void Insert(struct node *,int);
11. void Preorder(struct node *);
12. void Postorder(struct node *);
13. void Inorder(struct node *);
14. void Delete(struct node *,int);
15. struct node *Header;
16. int main()
17. {
18. int ch,x;
19. Header=(struct node*)malloc(sizeof(struct node));
20. Header->lptr=Header;
21. Header->rptr=Header;
22. do
23. {
24. printf("\n1.Insert a node in a Tree");
25. printf("\n2.Preorder Traversal(Recursively)");
26. printf("\n3.Postorder Traversal(Recursively)");
27. printf("\n4.Inorder Traversal(Recursively)");
28. printf("\n5.Delete a node from Binary Search Tree");
29. printf("\n6.Exit");
30. printf("\n\nEnter Choice: ");
31. scanf("%d",&ch);
32. switch(ch)
33. {
34. case 1:
35. printf("\n\tEnter Element : ");
36. scanf("%d",&x);
37. Insert(Header,x);
38. printf("\n\tInorder Traversal(Recursively)=\n\t");
39. printf("\n\t-------------------------------------\n\t");
40. Inorder(Header->lptr);
41. printf("\n\t-------------------------------------\n\t");
42. break;
43. case 2:
44. printf("\n\tPreorder Traversal(Recursively):\n\t");
45. printf("\n\t-------------------------------------\n\t");
46. Preorder(Header->lptr);
47. printf("\n\t-------------------------------------\n\t");
48. break;
49. case 3:
50. printf("\n\tPostorder Traversal(Recursively):\n\t");
51. printf("\n\t-------------------------------------\n\t");
52. Postorder(Header->lptr);
53. printf("\n\t-------------------------------------\n\t");
54. break;
55. case 4:
56. printf("\n\tInorder Traversal(Recursively):\n\t");
57. printf("\n\t-------------------------------------\n\t");
58. Inorder(Header->lptr);
59. printf("\n\t-------------------------------------\n\t");
60. break;
61. case 5:
62. printf("\n\tEnter Element which u want to Delete: ");
63. scanf("%d",&x);
64. printf("\n\t-------------------------------------\n\t");
65. Delete(Header,x);
66. printf("\n\t-------------------------------------\n\t");
67. break;
68. case 6: exit(0);
69. break;
70. default:
71. printf("\n\t Plz Try Again.");
72. }
73. }while(6);
74. }
75. void Insert(struct node *h,int x)
76. {
77. struct node *New,*parent,*cur;
78. New=(struct node *)malloc(sizeof(struct node));
79. if(New==NULL)
80. {
81. printf("\n\tNo Tree Node Available.");
82. return;
83. }
84. New->data=x;
85. New->lptr=NULL;
86. New->rptr=NULL;
87. if(h->lptr==h)
88. {
89. h->lptr=New;
90. return;
91. }
92. cur=h->lptr;
93. parent=h;
94. while(cur!=NULL)
95. {
96. if(x<cur->data)
97. {
98. parent=cur;
99. cur=cur->lptr;
100. }
101. else if(x>cur->data)
102. {
103. parent=cur;
104. cur=cur->rptr;
105. }
106. else
107. {
108. printf("\n\t Element Already Exist.\n");
109. return;
110. }
111. }
112. if(x<parent->data)
113. {
114. parent->lptr=New;
115. return;
116. }
117. if(x>parent->data)
118. {
119. parent->rptr=New;
120. return;
121. }
122. return;
123. }
124. void Preorder(struct node *t)
125. {
126. if(t!=NULL)
127. printf("%d ",t->data);
128. else
129. {
130. printf("\n\t Empty Tree.");
131. return;
132. }
133. if(t->lptr!=NULL)
134. Preorder(t->lptr);
135. if(t->rptr!=NULL)
136. Preorder(t->rptr);
137. return;
138. }
139. void Postorder(struct node *t)
140. {
141. if(t==NULL)
142. {
143. printf("\n\t Empty Tree.");
144. return;
145. }
146. Postorder(t->lptr);
147. Postorder(t->rptr);
148. printf("%d ",t->data);
149. return;
150. }
151. void Inorder(struct node *t)
152. {
153. if(t==NULL)
154. {
155. printf("\n\t Empty Tree.");
156. return;
157. }
158. if(t->lptr!=NULL)
159. Inorder(t->lptr);
160. printf("%d ",t->data);
161. if(t->rptr!=NULL)
162. Inorder(t->rptr);
163. return;
164. }
165. void Delete(struct node *h,int x)
166. {
167. int found;
168. char d;
169. struct node *cur,*parent,*pred,*suc,*q;
170. if(h->lptr==h)
171. {
172. printf("\n\t Empty Tree.");
173. return;
174. }
175. parent=h;
176. cur=h->lptr;
177. d='L';
178. found=0;
179. while(!found && cur!=NULL)
180. {
181. if(x==cur->data)
182. found=1;
183. else if(x<cur->data)
184. {
185. parent=cur;
186. cur=cur->lptr;
187. d='L';
188. }
189. else
190. {
191. parent=cur;
192. cur=cur->rptr;
193. d='R';
194. }
195. }
196. if(!found)
197. {
198. printf("\n\t Node is not found.");
199. return;
200. }
201. if(cur->lptr==NULL)
202. q=cur->rptr;
203. else
204. {
205. if(cur->rptr==NULL)
206. q=cur->lptr;
207. else
208. {
209. suc=cur->rptr;
210. if(suc->lptr==NULL)
211. {
212. suc->lptr=cur->lptr;
213. q=suc;
214. }
215. else
216. {
217. pred=cur->rptr;
218. suc=pred->lptr;
219. while(suc->lptr!=NULL)
220. {
221. pred=suc;
222. suc=pred->lptr;
223. }
224. pred->lptr=suc->rptr;
225. suc->lptr=cur->lptr;
226. suc->rptr=cur->rptr;
227. q=suc;
228. }
229. }
230. }
231. if(d=='L')
232. parent->lptr=q;
233. else
234. parent->rptr=q;
235. printf("\n\t%d is Deleted.",x);
236. }

 

Goto Home Page :