Binary search tree operations(insertion,deletion) cprogram
Aim: to implement binary search operation(insertion,deletion) in c program
program:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void insertion(int);
void display();
struct bsearch
{
int data;
struct bsearch *rchild,*lchild;
};
typedef struct bsearch node;
node *root,*ptr,*new,*parent,*temro;
void main()
{
int ch,item,rt,item2;
clrscr();
root=(node *)malloc(sizeof(node));
printf("enter the root for bst tree");
scanf("%d",&rt);
root->data=rt;
root->rchild=NULL;
root->lchild=NULL;
while(1)
{
printf("1.insert 2.delete 3.display 4.eixt");
printf("\tenter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter the item to insert");
scanf("%d",&item);
insertion(item);
break;
case 2:
printf("enter the item to be deleted");
scanf("%d",&item);
deletion(root,item);
break;
case 3:
printf("inoder=");
display(root);
printf("\n");
break;
default :
exit(0);
}
}
}
void insertion(int item)
{
ptr=root;
while(ptr!=NULL)
{
if(ptr->data==item)
{
printf("item already exit insertion not possible");
exit(0);
}
else if(item<ptr->data)
{
parent=ptr;
ptr=ptr->lchild;
}
else
{
parent=ptr;
ptr=ptr->rchild;
}
if(ptr==NULL)
{
new=(node *)malloc(sizeof(node));
new->data=item;
new->lchild=NULL;
new->rchild=NULL;
if(item<parent->data)
parent->lchild=new;
else
parent->rchild=new;
}
}
}
void display(struct bsearch *root)
{
if(root!=NULL)
{
display(root->lchild);
printf("%d ",root->data);
display(root->rchild);
}
}
deletion(struct bsearch *root,int item)
{
node *ptr1,*insuc;
int found=0,cas,temp;
ptr=root;
while(ptr!=NULL)
{
if(ptr->data==item)
{
found=1;
break;
}
else if(item<ptr->data)
{
parent=ptr;
ptr=ptr->lchild;
}
else
{
parent=ptr;
ptr=ptr->rchild;
}
}
if(found==0)
printf("item to be deleted is not found");
else
{
if(ptr->lchild==NULL&&ptr->rchild==NULL)
cas=1;
else if(ptr->lchild!=NULL&&ptr->rchild!=NULL)
cas=3;
else
cas=2;
}
if(cas==1)
{
if(parent->lchild->data==item)
{
parent->lchild=NULL;
free(ptr);
}
else
{
parent->rchild=NULL;
free(ptr);
}
}
if(cas==2)
{
if(parent->lchild->data==item)
{
if(ptr->lchild!=NULL)
{
parent->lchild=ptr->lchild;
free(ptr);
}
else
{
parent->lchild=ptr->rchild;
free(ptr);
}
}
else
{
if(ptr->lchild!=NULL)
{
parent->rchild=ptr->lchild;
free(ptr);
}
else
{
parent->rchild=ptr->rchild;
free(ptr);
}
}
}
if(cas==3)
{
ptr1=ptr->rchild;
while(ptr1!=NULL)
{
insuc=ptr1;
ptr1=ptr1->lchild;
}
temp=insuc->data;
ptr->data=temp;
deletion(insuc,temp);
}
}
output:
No comments:
Post a Comment