Level-Order Travsal BST(Program)

Level-Order Travsal

CODE

👇

//Main File

2. #include<stdio.h>
3. #include<stdlib.h>
4. #include "levelorder.h"  
5. 
   
6. void main()
7. {
8.     NODE *root=NULL;
9.     printf("\t>>First Create BST<<\n");
10.     root = createbst(root); 
11.     
12. display(root);
13.     
14. printf("\n\n\t>>Level order traversal<<\t");
15.     levelorder(root);
16. }

//Header File

1.   #define MAXSIZE 20
2.     typedef struct node
3.     {
4.      int info;
5.      struct node *left, *right;
6.     }NODE;
7. 
   
8.      //QUEUE FUNCTIONS
9.     typedef struct
10.     {
11.      NODE *data[MAXSIZE];
12.      int front, rear;
13.     }QUEUE;
14. 
    
15.     void initq(QUEUE *pq)
16.     {
17.      pq->front = pq->rear = -1;
18.     }
19. 
    
20.     void addq(QUEUE *pq, NODE *treenode)
21.     {
22.      pq->data[++pq->rear] = treenode;
23.     }
24. 
    
25.     NODE* removeq(QUEUE *pq)
26.     {
27.      return pq->data[++pq->front];
28.     }
29. 
    
30.     int isempty(QUEUE *pq)
31.     {
32.      return (pq->front == pq->rear);
33.     }
34. 
    
35.     int isfull(QUEUE *pq)
36.     {
37.      return(pq->rear == MAXSIZE-1);
38.     }
39. 
    
40. 
    
41. 
    
42.      //TREE FUNCTION
43.     NODE * createbst(NODE *root)
44.     {
45.      NODE *newnode, *temp, *parent;
46.      int i, n, num;
47.      printf("\nHow many nodes you want to enter?\t");
48.      scanf("%d", &n);
49.      printf("Enter the %d elements:\t", n);
50.      for(i=1; i<=n; i++)
51.      {
52.      newnode = (NODE*)malloc(sizeof (NODE));
53.      scanf("%d", &num);
54.      newnode->info=num;
55.      newnode->left = newnode->right = NULL;
56.      if(root == NULL)
57.      {
58.      root = newnode;
59.      continue;
60.      }
61.      temp = root;
62.      while(temp != NULL)
63.      {
64.      parent = temp;
65.      if(num < temp->info)
66.      temp = temp->left;
67.      else
68.      temp = temp->right;
69.      }
70.      if(num < parent->info)
71.      parent->left = newnode;
72.      else
73.      parent->right = newnode;
74.      }
75.      return(root);
76.     }
77. 
    
78. //DISPLAY 
79. void display(NODE *root)
80. {
81. NODE *temp=root;
82. if(temp != NULL)
83. {
84. printf("\t%d",temp->info);
85. display(temp->left);
86. display(temp->right);
87. }
88. }
89. 
    
90. //Level Order
91.     void levelorder(NODE *root)
92.     {
93.      int i, level=0;
94.      NODE *temp, *marker=NULL;
95.      QUEUE q;
96.      initq(&q);
97.      addq(&q, root);
98.      addq(&q, marker);
99.      printf("\nLevel %d --->\t", level);
100.      while(!isempty(&q))
101.      {
102.      temp = removeq(&q);
103.      if(temp == marker)
104.      {
105.      level++;
106.      if(!isempty(&q))
107.      {
108.      addq(&q, marker);
109.      printf("\nLevel %d --->\t", level);
110.      }
111.      }
112.      else
113.      {
114.      printf("%d\t", temp->info);
115.      if(temp->left)
116.      addq(&q, temp->left);
117.      if(temp->right)
118.      addq(&q, temp->right);
119.      }
120.      }
121.      printf("\n\nTotal Level In BST:-\t%d",level);
122.     }

//Output

/*

        >>First Create BST<<

How many nodes you want to enter?       5

Enter the 5 elements:   10

65

39

42

91

        >>Level order traversal<<

Level 0 --->10

Level 1 --->65

Level 2 --->39  91

Level 3 --->42

Total Level In BST:-  4

*/

                                                                                                                                                                                                                                                   //ThE ProFessoR