Create a Binary Search Tree of integers and perform the following operations (i)insert (ii) delete (iii). Search (iv) traversals (pre-order, in-order, post-order) BST
#include<stdio.h>
struct node
{
int data;
struct node *lchild,*rchild;
}*root,*ptr,*parent,*new,*ptr1,*x,*y,*p;
void insert(int);
void delete(int);
void search(int);
void inorder(struct node *);
void preorder(struct node *);
void postorder(struct node *);
struct node* insucc(struct node *);
int main()
{
int ch,item,key;
root=NULL;
while(1)
{
printf("\nEnter Your Choice\n1.Insert\n2.Delete\n3.Search\n4.Inorder\n5.Preorder\n6.Postorder\n7.Exit");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("Enter item:");
scanf("%d",&item);
insert(item);
break;
case 2:printf("Enter item:");
scanf("%d",item);
delete(item);
break;
case 3: printf("Enter Key To Search:");
scanf("%d",&key);
search(key);
break;
case 4:inorder(root);
break;
case 5:preorder(root);
break;
case 6:postorder(root);
break;
default:exit(0);
}
}
}
void inorder(struct node *root)
{
if(root!=NULL)
{
inorder(root->lchild);
printf("%d\t",root->data);
inorder(root->rchild);
}
}
void preorder(struct node *root)
{
if(root!=NULL)
{
printf("%d\t",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}
void postorder(struct node *root)
{
if(root!=NULL)
{
postorder(root->lchild);
postorder(root->rchild);
printf("%d\t",root->data);
}
}
void insert(int item)
{
int flag=0;
ptr=root;
while(ptr!=NULL && flag==0)
{
if(item==ptr->data)
{
printf("Element Already Exists");
flag=1;
}
else if(item<ptr->data)
{
ptr1=ptr;
ptr=ptr->lchild;
}
else if(item>ptr->data)
{
ptr1=ptr;
ptr=ptr->rchild;
}
}
if (ptr==NULL)
{
new=(struct node*)malloc(sizeof(struct node));
new->lchild=NULL;
new->data=item;
new->rchild=NULL;
if (root==NULL)
root=new;
else if(item<ptr1->data)
ptr1->lchild=new;
else if(item>ptr1->data)
ptr1->rchild=new;
}
}
void delete(int item)
{
int flag=0,ch,key;
ptr=root;
while(ptr!=NULL && flag==0)
{
if(item==ptr->data)
{
printf("Element Found");
flag=1;
break;
}
else if(item<ptr->data)
{
parent=ptr;
ptr=ptr->lchild;
}
else if(item>ptr->data)
{
parent=ptr;
ptr=ptr->rchild;
}
}
if(flag==0)
printf("\nkey not found");
else
{
if(ptr->lchild==NULL && ptr->rchild==NULL)
ch=1;
else if(ptr->lchild!=NULL && ptr->rchild==NULL)
ch=2;
else
ch=3;
}
if(ch==1)
{
if(parent->lchild==ptr)
parent->lchild=NULL;
else
parent->rchild=NULL;
free(ptr);
if(ch==2)
{
if(parent->lchild==ptr)
{
if(parent->lchild==NULL)
parent->lchild=ptr->rchild;
else
parent->lchild=ptr->lchild;
}
else
{
if(ptr->lchild==NULL)
parent->rchild=ptr->rchild;
else
parent->rchild=ptr->lchild;
}
free(ptr);
}
else if (ch==3)
{
x=ptr;
y=insucc(ptr);
key=y->data;
delete(key);
x->data=key;
}
}
}
struct node *insucc(struct node *z)
{
p=z->rchild;
if (p!=NULL)
{
while(p->lchild==NULL)
p=p->lchild;
}
return p;
}
void search (int key)
{
int flag=0;
ptr=root;
while(ptr!=NULL)
{
if(key==ptr->data)
{
printf("Key Found");
flag=1;
break;
}
else if(key<ptr->data)
ptr=ptr->lchild;
else if (key>ptr->data)
ptr=ptr->rchild;
}
if (flag==0)
printf("Key Not Found");
}
Comments
Post a Comment