Write a program to implement following function on a Binary Search Tree
1. Insert
2. delete
3. Find Minimum
4. Find Max
5. inorder Traversal
6. Preorder traversal
7. Postorder Traversal
code👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👌👌👌
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
}*root;
void find(int item,struct node **par,struct node **loc)
{
struct node *ptr,*ptrsave;
if(root==NULL)
{
*loc=NULL;
*par=NULL;
return;
}
if(item==root->data)
{
*loc=root;
*par=NULL;
return;
}
if(item<root->data)
ptr=root->left;
else
ptr=root->right;
ptrsave=root;
while(ptr!=NULL)
{
if(item==ptr->data)
{ *loc=ptr;
*par=ptrsave;
return;
}
ptrsave=ptr;
if(item<ptr->data)
ptr=ptr->left;
else
ptr=ptr->right;
}
*loc=NULL;
*par=ptrsave;
}
void insert(int item)
{
struct node *temp,*parent,*location;
find(item,&parent,&location);
if(location!=NULL)
{
printf("\nITEM ALREADY PRESENT\n");
return;
}
temp=(struct node *)malloc(sizeof(struct node));
temp->data=item;
temp->left=NULL;
temp->right=NULL;
if(parent==NULL)
root=temp;
else
if(item<parent->data)
parent->left=temp;
else
parent->right=temp;
}
void case_a(struct node *par,struct node *loc )
{
if(par==NULL)
root=NULL;
else
if(loc==par->left)
par->left=NULL;
else
par->right=NULL;
}
void case_b(struct node *par,struct node *loc)
{
struct node *child;
if(loc->left!=NULL)
child=loc->left;
else
child=loc->right;
if(par==NULL )
root=child;
else
if( loc==par->left)
par->left=child;
else
par->right=child;
}
void case_c(struct node *par,struct node *loc)
{
struct node *ptr,*ptrsave,*suc,*parsuc;
ptrsave=loc;
ptr=loc->right;
while(ptr->left!=NULL)
{
ptrsave=ptr;
ptr=ptr->left;
}
suc=ptr;
parsuc=ptrsave;
if(suc->left==NULL && suc->right==NULL)
case_a(parsuc,suc);
else
case_b(parsuc,suc);
if(par==NULL)
root=suc;
else
if(loc==par->left)
par->left=suc;
else
par->right=suc;
suc->left=loc->left;
suc->right=loc->right;
}
void delete(int item)
{
struct node *parent,*location;
if(root==NULL)
{
printf("\nTREE IS EMPTY\n");
return;
}
find(item,&parent,&location);
if(location==NULL)
{
printf("\nITEM NOT FOUND\n");
return;
}
if(location->left==NULL && location->right==NULL)
case_a(parent,location);
if(location->left!=NULL && location->right==NULL)
case_b(parent,location);
if(location->left==NULL && location->right!=NULL)
case_b(parent,location);
if(location->left!=NULL && location->right!=NULL)
case_c(parent,location);
free(location);
}
void preorder(struct node *ptr)
{
if(root==NULL)
{
printf("\nTREE IS EMPTY\n");
return;
}
if(ptr!=NULL)
{
printf("%d ",ptr->data);
preorder(ptr->left);
preorder(ptr->right);
}
}
void inorder(struct node *ptr)
{
if(root==NULL)
{
printf("\nTREE IS EMPTY\n");
return;
}
if(ptr!=NULL)
{
inorder(ptr->left);
printf("%d ",ptr->data);
inorder(ptr->right);
}
}
void postorder(struct node *ptr)
{
if(root==NULL)
{
printf("\nTREE IS EMPTY\n");
return;
}
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
printf("%d ",ptr->data);
}
}
void minimum(struct node *root)
{
if(root==NULL)
{
printf("\nTREE IS EMPTY\n");
return;
}
else
{
while(root!=NULL && root->left!=NULL)
{
root=root->left;
}
printf("\nMINIMUM VALUE IN THE TREE IS:- %d\n",root->data);
}
}
void maximum(struct node *root)
{
if(root==NULL)
{
printf("\nTREE IS EMPTY\n");
return;
}
else
{
while(root!=NULL && root->right!=NULL)
{
root=root->right;
}
printf("\nMAXIMUM VALUE IN THE TREE IS:- %d\n",root->data);
}
}
void quit()
{
printf("\nTHANK YOU FOR USING THIS PROGRAM\nSUBMITTED BY ABHIJAY KRISHNA\n");
}
int main()
{
int choice,num;
root=NULL;
do
{
printf("\n1.INSERTION\n2.DELETION\n3.INORDER TRAVERSAL\n4.POSTORDER TRAVERSAL\n5.PREORDER TRAVERSAL\n6.FIND MINIMUM VALUE\n7.FIND MAXIMUM VALUE\n8.EXIT\nENTER YOUR CHOICE:- ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nENTER THE VALUE YOU WANT TO INSERT:- ");
scanf("%d",&num);
insert(num);
break;
case 2:
printf("\nENTER THE VALUE YOU WANT TO DELETE:- ");
scanf("%d",&num);
delete(num);
break;
case 3:
printf("\nINORDER TRAVERSAL IS:- ");
inorder(root);
printf("\n");
break;
case 4:
printf("\nPOSTORDER TRAVERSAL IS:- ");
postorder(root);
printf("\n");
break;
case 5:
printf("\nPREORDER TRAVERSAL IS:- ");
preorder(root);
printf("\n");
break;
case 6:
minimum(root);
break;
case 7:
maximum(root);
break;
case 8:
quit();
break;
default:
printf("\nOOPS YOU HAVE ENTERED A WRONG CHOICE!!!\nPLEASE TRY AGAIN\n");
}
}while(choice!=8);
}
No comments:
Post a Comment