Binary Sorted Tree : Source Code

1. #include
2. #include
3. #include
4. struct tree
5. {
6. int data;
7. tree *left;
8. tree *right;
9. }*root;
10.  
12. void main()
13. {
14. root=NULL;
15. int d;
16. void add();
17. void traverse(tree *);
18. tree* del(tree *,int);
19. int c;
20. do
21. {
22. printf("\nM A I N M E N U ");
23. printf("\n=====================");
24. printf("\n1. Add a node ");
25. printf("\n2. Display tree");
26. printf("\n3. Delete a node");
27. printf("\n4. Quit");
28. printf("\nSelect your choice ");
29. scanf("%d",&c);
30. if(c==1)
31. add();
32. else if(c==2)
33. traverse(root);
34. else if(c==3)
35. {
36. printf("\nEnter data to delete ");
37. scanf("%d",&d);
38. root=del(root,d);
39. }
40. }while(c!=4);
41. }
42.  
43. void add()
44. {
45. printf("\nAdd a node ");
46. tree *t,*prev;
47. tree *search(tree *,int);
48. t=(tree *)malloc(sizeof(tree));
49. printf("\nEnter data ");
50. scanf("%d",&t->data);
51. if(root==NULL)
52. {
53. root=t;
54. t->left=NULL;
55. t->right=NULL;
56. }
57. else
58. {
59. prev=search(root,t->data);
60. if(prev==NULL)
61. {
62. printf("\nNode already exists");
63. return;
64. }
65. else if(prev->data>t->data)
66. {
67. prev->left=t;
68. }
69. else
70. prev->right=t;
71. t->left=NULL;
72. t->right=NULL;
73. }
74. printf("\nNode Added ");
75. }
76.  
77. tree *search(tree *r,int d)
78. {
79. tree *prev;
80. while(r!=NULL)
81. {
82. if(r->data==d)
83. return NULL;
84. else if(r->data>d)
85. {
86. prev=r;
87. r=r->left;
88. }
89. else
90. {
91. prev=r;
92. r=r->right;
93. }
94. }
95. return prev;
96. }
97. void traverse(tree *r)
98. {
99. if(r==NULL)
100. return;
101. traverse(r->left);
102. printf("\n%d",r->data);
103. traverse(r->right);
104. }
105. tree *del(struct tree *root, int key)
106. {
107. tree *p,*p2;
108. if(!root)
109. return root;
110. if(root->data == key)
111. {
112. if(root->left == root->right){
113. free(root);
114. return NULL;
115. }
116. else if (root->left == NULL)
117. {
118. p = root->right;
119. free(root);
120. return p;
121. }
122. else if(root->right == NULL)
123. {
124. p = root->left;
125. free(root);
126. return p;
127. }
128. else
129. {
130. p2 = root->right;
131. p = root->right;
132. while(p->left)
133. p = p->left;
134. p->left = root->left;
135. free(root);
136. return p2;
137. }
138. }
139. if(root->data < key)
140. root->right = del(root->right, key);
141. else
142. root->left = del(root->left, key);
143. return root;
144. }