Binary Search Tree With Level Order Traversal

/*Binary Search Tree with level order traversal ... Queue for level order traversal is implemented using linked list*/

#include<stdio.h>
#include<stdlib.h>

typedef struct BinarySearchTree
{
struct BinarySearchTree *left;
struct BinarySearchTree *right;
int val;
}bst;

typedef struct Queue
{
bst *val;
struct Queue *next;
}qu;

void enqueu(qu **,bst *);
bst *dequeu(qu **);
int isempty(qu *);





bst * create(bst *,int);

void inorder(bst *);
void preorder(bst *);
void postorder(bst *);
void levelorder(bst *);


int main()
{
bst *root=NULL;
int g,ch;
while(1)
{
printf("\n 1) Insert\n 2) Preorder traversal\n 3) Inorder traversal\n 4) Postorder traversal\n 5) Level Order Traversal\n 6) Exit");
printf("\n Enter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nInsert value for the tree: ");
scanf("%d",&g);
root=create(root,g);
break;
case 2: printf("\nValues in Preorder Traversal : ");
preorder(root);
break;
case 3: printf("\nValues in Inorder Traversal : ");
inorder(root);
break;
case 4: printf("\nValues in Postorder Traversal : ");
postorder(root);
break;
case 5: printf("\nValues in Level order Traversal : ");
levelorder(root);
break;
case 6:
exit(0);
}
}
}


bst *create(bst *root,int p)
{
bst *temp,*pre,*ptr;

temp=(bst *)malloc(sizeof(bst));
temp->val=p;
temp->right=temp->left=NULL;
if(root==NULL)
{
root=temp;
}
else
{
ptr=root;
while(ptr!=NULL)
{
pre=ptr;
if(ptr->val>p)
ptr=ptr->left;
else
ptr=ptr->right;
}
if(pre->val>p)
pre->left=temp;
else
pre->right=temp;
}
return root;
}


void preorder(bst *root)
{
if(root!=NULL)
{
printf("%d,",root->val);
preorder(root->left);
preorder(root->right);
}
}

void inorder(bst *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d,",root->val);
inorder(root->right);
}
}

void postorder(bst *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d,",root->val);
}
}




void levelorder(bst *root)
{
qu *p=NULL;
bst *ptr;
enqueu(&p,root);
while(!isempty(p))
{
ptr=dequeu(&p);
printf("%d,",ptr->val);
if(ptr->left!=NULL)
enqueu(&p,ptr->left);
if(ptr->right!=NULL)
enqueu(&p,ptr->right);
}
}



void enqueu(qu **p,bst *ptr1)
{
qu *temp,*ptr;
temp=(qu *)malloc(sizeof(qu));
temp->val=ptr1;
temp->next=NULL;
if(*p==NULL)
*p=temp;
else
{
ptr=*p;
while(ptr->next!=NULL)
ptr=ptr->next;

ptr->next=temp;
}
}


bst *dequeu(qu **p)
{
bst *ptr;
ptr=(*p)->val;
*p=(*p)->next;
return ptr;
}



int isempty(qu *p)
{
if(p==NULL)
return 1;
else
return 0;
}


I/O:



Comments

Popular posts from this blog

Pascal Triangle using 2D array

JAVA program to add two distance