· 6 years ago · Oct 18, 2019, 08:54 PM
1#include<stdio.h>
2#include<stdlib.h>
3
4typedef struct node{
5 int key;
6 struct node *left, *right;
7} Node;
8
9Node *newNode(int item){
10 Node *temp = (Node *)malloc(sizeof(Node));
11 temp->key = item;
12 temp->left = temp->right = NULL;
13 return temp;
14}
15
16
17Node* insert(Node* root, int key){
18 // Create a new Node containing
19 // the new element
20 Node* newnode = newNode(key);
21 // Pointer to start traversing from root and
22 // traverses downward path to search
23 // where the new node to be inserted
24 Node* x = root;
25 // Pointer y maintains the trailing
26 // pointer of x
27 Node* y = NULL;
28 while (x != NULL){
29 y = x;
30 if (key < x->key)
31 x = x->left;
32 else
33 x = x->right;
34 }
35 // If the root is NULL i.e the tree is empty
36 // The new node is the root node
37 if (y == NULL)
38 y = newnode;
39 // If the new key is less then the leaf node key
40 // Assign the new node to be its left child
41 else if (key < y->key)
42 y->left = newnode;
43 // else assign the new node its right child
44 else
45 y->right = newnode;
46 // Returns the pointer where the
47 // new node is inserted
48 if(root == NULL)
49 return y;
50 else
51 return root;
52}
53
54int search(Node* root, int key1){
55 // Traverse untill root reaches to dead end
56 Node* tmp = root;
57 while (tmp != NULL) {
58 // pass right subtree as new tree
59 if (key1 > tmp->key)
60 tmp = tmp->right;
61 // pass left subtree as new tree
62 else if (key1 < tmp->key)
63 tmp = tmp->left;
64 else
65 return 1; // if the key is found return 1
66 }
67 return 0;
68}
69
70struct qnode{
71 Node *nd;
72 struct qnode *ptr;
73} *frontQ, *rearQ, *tempQ, *front1Q;
74
75
76void enq(Node* n){
77 if (rearQ == NULL){
78 rearQ = (struct qnode *)malloc(1*sizeof(struct qnode));
79 rearQ->ptr = NULL;
80 rearQ->nd = n;
81 frontQ = rearQ;
82 }else{
83 tempQ = (struct qnode *)malloc(1*sizeof(struct qnode));
84 rearQ->ptr = tempQ;
85 tempQ->nd = n;
86 tempQ->ptr = NULL;
87 rearQ = tempQ;
88 }
89}
90
91void deq(){
92 front1Q = frontQ;
93 if (front1Q == NULL){
94 printf("\n Error: Trying to display elements from empty queue");
95 return;
96 }else
97 if (front1Q->ptr != NULL){
98 front1Q = front1Q->ptr;
99 free(frontQ);
100 frontQ = front1Q;
101 } else {
102 free(frontQ);
103 frontQ = NULL;
104 rearQ = NULL;
105 }
106}
107
108int empty(){
109 if ((frontQ == NULL) && (rearQ == NULL))
110 return 1;
111 else
112 return 0;
113}
114
115void deleteBST(Node* root){
116 // empty tree
117 if (root == NULL)
118 return;
119 // create an empty queue and enqueue root node
120 //queue<Node*> queue;
121 enq(root);
122 Node *frontN = NULL;
123 // run till queue is not empty
124 while (!empty()) {
125 // delete each node in the queue one by one after pushing their
126 // non-empty left and right child to the queue
127 frontN = frontQ->nd;
128 deq();
129 if (frontN->left)
130 enq(frontN->left);
131
132 if (frontN->right)
133 enq(frontN->right);
134 // Important - delete front node ONLY after enqueuing its children
135 free(frontN);
136 }
137}
138
139void printBST(Node* root){
140 if (root != NULL && root != 0){
141 enq(root);
142 Node *frontN = NULL;
143 // run till queue is not empty
144 while (!empty()) {
145 // delete each node in the queue one by one after pushing their
146 // non-empty left and right child to the queue
147 frontN = frontQ->nd;
148 deq();
149 if (frontN->left)
150 enq(frontN->left);
151
152 if (frontN->right)
153 enq(frontN->right);
154 // Important - delete front node ONLY after enqueuing its children
155 printf("%d ", frontN->key);
156 }
157 printf("\n");
158 // set root as NULL before returning
159 //root = NULL;
160 }
161}
162
163Node* rotate(Node* root,int key1, int right){
164 // Traverse untill root reaches to dead end
165 Node* x = root, *prev = NULL;
166 while (x != NULL) {
167 // pass right subtree as new tree
168 if (key1 > x->key){
169 prev = x;
170 x = x->right;}
171 // pass left subtree as new tree
172 else if (key1 < x->key){
173 prev = x;
174 x = x->left;}
175 else break;
176 }
177
178 if( x == NULL){
179 printf("Given node doesn't exists\n");
180 return root;
181 }
182 Node *y = NULL, *tmp = NULL;
183
184 if(right && x->left==NULL){//Rotacija u desno i nemamo levog sina -> nista se ne radi
185 return root;
186 }else if(!right && x->right==NULL){//Rotacija u levo i nemamo desnog sina -> nista se ne radi
187 return root;
188 }
189
190 if(right){
191 y = x->left;
192 tmp = y->right;
193 y->right = x;
194 x->left = tmp;
195 }else{
196 y = x->right;
197 tmp = y->left;
198 y->left = x;
199 x->right = tmp;
200 }
201 if( x == root ) {root = y;}
202 else if(prev->right == x) prev->right = y;
203 else if(prev->left == x) prev->left = y;
204 return root;
205}
206
207struct StackNode {
208 int low;
209 int high;
210 struct StackNode* next;
211} *top;
212
213// Utility function to add an element data in the stack
214 // insert at the beginning
215void push(int l, int h){
216 // create new node temp and allocate memory
217 struct StackNode *sn = (struct StackNode*)malloc(sizeof(struct StackNode));
218 sn->low = l;
219 sn->high = h;
220 sn->next = top;
221 top = sn;
222}
223
224// Utility function to check if the stack is empty or not
225int StackEmpty(){
226 return top == NULL;
227}
228
229// Utility function to pop top
230// element from the stack
231struct StackNode *pop(){
232 // check for stack underflow
233 if (top == NULL) {
234 printf("\nStack Underflow");
235 exit(1);
236 }
237 else {
238 struct StackNode *temp;
239 // top assign into temp
240 temp = top;
241 // assign second node to top
242 top = top->next;
243 // destroy connection between first and second
244 temp->next = NULL;
245 return temp;
246 }
247}
248
249Node *formBST(int* table, int* valid){
250 int low = 0, high = 11;//sizeof(table)/sizeof(int); !!!!!!!!!!!!!!!!
251 int mid = high/2;
252 Node *toor = NULL;
253 push(low, high);
254
255 while(!StackEmpty()){
256
257 struct StackNode *tmp = pop();
258 low = tmp->low;
259 high = tmp->high;
260
261 if(high < low) continue;
262 else if( low == high )
263 if(valid[low] == 1){
264 toor = insert(toor, table[low]);
265 continue;
266 }
267
268
269 mid = (low+high) / 2;
270 if(valid[mid] == 1)
271 toor = insert(toor, table[mid]);
272
273 push(mid+1, high);
274 push(low,mid-1);
275 }
276
277 return toor;
278}
279
280int main(){
281
282 frontQ = rearQ = NULL;
283 Node *root = NULL;
284
285 //___________TESTING___________
286
287 root = insert(root, 50);
288 insert(root, 30);
289 insert(root, 20);
290 insert(root, 40);
291 insert(root, 70);
292 insert(root, 60);
293 insert(root, 80);
294
295 printBST(root);
296
297 if (search(root, 30))
298 printf("\nYes\n");
299 else
300 printf("\nNo");
301
302
303 deleteBST(root);
304 root = NULL;
305
306 printBST(root);
307
308 root = insert(root, 4);
309 insert(root, 2);
310 insert(root, 6);
311 insert(root, 3);
312 insert(root, 1);
313 printBST(root);
314 printf("\n");
315
316 deleteBST(root);
317
318 int table[]={3,3,4,5,7,9,9,9,10,10,14};
319 int valid[]={1,0,1,1,1,1,0,0,1,0,1};
320
321 root = formBST(table, valid);
322
323 printBST(root);
324 printf("\n");
325
326 // ^^^^^ TESTING ^^^^^^^^
327
328 int flag = 1, ch, n;
329
330 while(flag == 1){
331 printf("-===Menu===-");
332 printf("\n 1 - Form BST");
333 printf("\n 2 - Search");
334 printf("\n 3 - Insert into BST");
335 printf("\n 4 - Display BST");
336 printf("\n 5 - Delete BST");
337 printf("\n 6 - Rotate left");
338 printf("\n 7 - Rotate right");
339 printf("\n 0 - Exit");
340
341 printf("\n Enter choice : ");
342 scanf("%d", &ch);
343
344 switch(ch){
345 case 1:
346 root = formBST(table,valid);
347 printf("The BST is formed.\n");
348 break;
349 case 2:
350 printf("Insert the key: ");
351 scanf("%d", &n);
352 if (search(root, n))
353 printf("\n The key exists in BST.\n");
354 else
355 printf("\nThe key doesnt exists in BST.\n");
356 break;
357 case 3:
358 printf("Insert the key: ");
359 scanf("%d", &n);
360 root = insert(root, n);
361 break;
362 case 4:
363 printBST(root);
364 break;
365 case 5:
366 deleteBST(root);
367 root = NULL;
368 break;
369 case 6:
370 printf("Insert the key: ");
371 scanf("%d", &n);
372 root = rotate(root, n, 0);
373 break;
374 case 7:
375 printf("Insert the key: ");
376 scanf("%d", &n);
377 root = rotate(root, n, 1);
378 break;
379 case 0:
380 deleteBST(root);
381 flag = 0;
382 break;
383 default:
384 printf("Wrong choice, Please enter correct choice");
385 break;
386 }
387 }
388 return 0;
389}