Binary Search Tree Creation and Level-order, Inorder, Preorder, Postorder Traversals
#include<stdio.h>
#include<stdlib.h>
struct
BST
{
int
data;
struct BST *lchild;
struct BST *rchild;
};
typedef struct BST * NODE;
NODE get_node()
{
NODE
temp;
temp
= (NODE) malloc(sizeof(struct BST));
temp->lchild
= NULL;
temp->rchild
= NULL;
return
temp;
}
void insert(NODE root, NODE newnode)
{
if
(newnode->data < root->data)
{
if
(root->lchild == NULL)
root->lchild
= newnode;
else
insert(root->lchild, newnode);
}
if
(newnode->data > root->data)
{
if
(root->rchild == NULL)
root->rchild
= newnode;
else
insert(root->rchild, newnode);
}
}
void inorder(NODE root)
{
if(root
!= NULL)
{
inorder(root->lchild);
printf("%d
", root->data);
inorder(root->rchild);
}
}
void preorder(NODE root)
{
if
(root != NULL)
{
printf("%d
", root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}
void postorder(NODE root)
{
if
(root != NULL)
{
postorder(root->lchild);
postorder(root->rchild);
printf("%d
", root->data);
}
}
void levelorder(NODE root)
{
NODE
q[40],cur;
int
front=0,rear=-1;
q[++rear]=root;
while(front<=rear)
{
cur
= q[front++];
printf("%d
",cur->data);
if(cur->lchild
!= NULL)
q[++rear]
= cur->lchild;
if(cur->rchild
!= NULL)
q[++rear]
= cur->rchild;
}
}
void main()
{
int val, i,n;
NODE
root = NULL, newnode;
printf("\nEnter the
number of elements: ");
scanf("%d", &n);
for(i=1;
i<=n; i++)
{
newnode
= get_node();
printf("\nEnter
The node value: ");
scanf("%d",
&val);
newnode->data =
val;
if
(root == NULL)
root
= newnode;
else
insert(root,
newnode);
}
if (root == NULL)
printf("\nTree
Is Not Created");
else
{
printf("\nThe
Levelorder display : ");
levelorder(root);
printf("\nThe
Inorder display : ");
inorder(root);
printf("\nThe
Preorder display : ");
preorder(root);
printf("\nThe
Postorder display : ");
postorder(root);
}
}
Output:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
The
Levelorder display : 6 5 9
2 8 15 7 14
24
The
Inorder display : 2 5 6
7 8 9 14 15
24
The
Preorder display : 6 5 2
9 8 7 15 14
24
The
Postorder display : 2 5 7
8 14 24 15 9
6