DATA STRUCTURES-POINTER IMPLEMENTATION OF BINARY SEARCH TREE

PROGRAM CODING:-

typedef int elttype;
#include<stdio.h>
#include<stdlib.h>
struct bst
{
elttype data;
struct bst *left,*right;
};
struct bst * makeempty(struct bst *t)
{
if(t!=NULL)
{
makeempty(t->left);
makeempty(t->right);
free(t);
}
return NULL;
}
void dispose(struct bst *t)
{
makeempty(t);
free(t);
}
struct bst * find(elttype x,struct bst *t)
{
if(t==NULL)
return NULL;
if(x<t->data)
return(find(x,t->left));
else if(x>t->data)
return(find(x,t->right));
else
return t;
}
struct bst * findmin(struct bst *t)
{
if(t->left==NULL)
return t;
else return findmin(t->left);
}
struct bst * findmax(struct bst *t)
{
if(t->right==NULL)
return t;
else return findmax(t->right);
}
struct bst * insert(elttype x,struct bst *t)
{
if(t==NULL)
{
t=(struct bst *)malloc(sizeof(struct bst));
t->data=x;
t->left=t->right=NULL;
}
else if(x<t->data)
t->left=insert(x,t->left);
else if(x>t->data)
t->right=insert(x,t->right);
else if(x==t->data)
printf("Updated message:Element already present tree...No change made to tree!**!");
return t;
}
struct bst * delet(elttype x,struct bst *t)
{
struct bst *temp;
if(t==NULL)
printf("Deletion failure:Element not found!**!");
else
{
if(x<t->data)
t->left=delet(x,t->left);
else if(x>t->data)
t->right=delet(x,t->right);
else if(t->left && t->right)
{
temp=findmin(t->right);
t->data=temp->data;
t->right=delet(t->data,t->right);
}
else
{
temp=t;
if(t->left==NULL)
t=t->right;
else if(t->right==NULL)
t=t->left;
free(temp);
printf("Deletion successful!**!");
}
}
return t;
}
void preorder(struct bst *root)
{
if(root!=NULL)
{
printf("%d\t",root->data);
preorder(root->left);
preorder(root->right);
}
}
void inorder(struct bst *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d\t",root->data);
inorder(root->right);
}
}
void postorder(struct bst *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d\t",root->data);
}
}
int main()
{
struct bst *root,*tmp;
int ch,ch1;
elttype datum;
root=NULL;
while(1)
{
printf("\nBINARY SEARCH TREE MAIN MENU:\n\t1.Insert\n\t2.Delete\n\t3.Traversal menu\n\t4.Search\n\t5.Find min\n\t6.Find max\n\t7.Make empty\n\t8.Delete tree and exit\nChoice:");
scanf("%d",&ch);
if(ch==8)
break;
switch(ch)
{
case 1:
printf("Enter the data to inserted: ");
scanf("%d",&datum);
root=insert(datum,root);
printf("Insertion successful!**!");
break;
case 2:
if(root!=NULL)
{
printf("Enter the data to be deleted: ");
scanf("%d",&datum);
root=delet(datum,root);
}
else printf("Deletion failure:Search tree is empty!**!");
break;
case 3:
while(1)
{
if(root==NULL)
{
printf("Traversal Failure:Search Tree is empty=>No traversal possible!**!");
break;
}
printf("\nTRAVERSAL MENU:\n\t1.Preorder\n\t2.Inorder\n\t3.Postorder\n\t4.Back to main menu\nChoice: ");
scanf("%d",&ch1);
if(ch1==4)
break;
switch(ch1)
{
case 1:
printf("Preorder traversal:\n");
preorder(root);
break;
case 2:
printf("Inorder traversal:\n");
inorder(root);
break;
case 3:
printf("Postorder traversal:\n");
postorder(root);
break;
}
}
break;
case 4:
if(root!=NULL)
{
printf("Enter the data to be searched:");
scanf("%d",&datum);
tmp=find(datum,root);
if(tmp==NULL)
printf("Search failure:Value not found!**!");
else
printf("Value found");
}
else printf("Search Failure:Search tree is empty!**!");
break;
case 5:
tmp=findmin(root);
if(root!=NULL)
{
if(tmp==NULL)
printf("Search tree is empty!**!");
else
printf("Minimum value: %d",tmp->data);
}
else printf("Search tree is empty!**!!");
break;
case 6:
tmp=findmax(root);
if(root!=NULL)
{
if(tmp==NULL)
printf("Search tree is empty!**!");
else
printf("Maximum value: %d",tmp->data);
}
else printf("Search tree is empty!**!");
break;
case 7:
if(root==NULL)
printf("Search tree is already empty!**!");
else
{
root=makeempty(root);
printf("Search tree made empty!**!");
}
break;
}
}
return 0;
}