Wednesday, 26 September 2012

Binary search tree using c program

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define NULL 0
struct node
{
struct node *lchild;
int info;
struct node *rchild;
}*root;
void find(int,struct node **,struct node **);
void insert(int);
void del(int);
void case_a(struct node *,struct node *);
void case_b(struct node *,struct node *);
void case_c(struct node *,struct node *);
void preorder(struct node *);
void postorder(struct node *);
void inorder(struct node *);
void main(void)
{
int choice,num;
root=NULL;
clrscr();
do
{
printf("\n");
printf("\n1-insert");
printf("\n2-delete");
printf("\n3-inorder");
printf("\n4-preorder");
printf("\n5-postorder");
printf("\n6-quit");
printf("\nenter your choice");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nenter number to be inserted:");
scanf("%d",&num);
insert(num);
break;
case 2:
printf("\nenter number to be deleted");
scanf("%d",&num);
del(num);
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
default:
break;
}
}while(choice<=5);
}
void find(int item,struct node **par,struct node **loc)
{
struct node *ptr,*ptr1;
if(root==NULL)
{
*loc=NULL;
*par=NULL;
return;
}
if(item==root->info)
{
*loc=root;
ptr=NULL;
return;
}
if(item<root->info)
ptr=root->lchild;
else
ptr=root->rchild;
ptr1=root;
while(ptr!=NULL)
{
if(item==ptr->info)
{
*loc=ptr;
*par=ptr1;
return;
}
ptr1=ptr;
if(item<ptr->info)
ptr=ptr->lchild;
else
ptr=ptr->rchild;
}
*loc=NULL;
*par=ptr1;
}
void insert(int item)
{
struct node *newnode,*parent,*location;
find(item,&parent,&location);
if(location!=NULL)
{
printf("\nitem is already present");
return;
}
newnode=(struct node*)malloc(sizeof(struct node));
newnode->info=item;
newnode->lchild=NULL;
newnode->rchild=NULL;
if(parent==NULL)
root=newnode;
else
{
if(item<parent->info)
parent->lchild=newnode;
else
parent->rchild=newnode;
}
}
void preorder(struct node *ptr)
{
if(root==NULL)
{
printf("\ntree is empty");
return;
}
if(ptr!=NULL)
{
printf("%d-->",ptr->info);
preorder(ptr->lchild);
preorder(ptr->rchild);
}.
}
void inorder(struct node *ptr)
{
if(root==NULL)
{
printf("\ntree is empty");
return;
}
if(ptr!=NULL)
{
inorder(ptr->lchild);
printf("%d-->",ptr->info);
inorder(ptr->rchild);
}
}
void postorder(struct node *ptr)
{
if(root==NULL)
{
printf("\ntree is empty");
return;
}
if(ptr!=NULL)
{
postorder(ptr->lchild);
postorder(ptr->rchild);
printf("%d-->",ptr->info);
}
}
void del(int item)
{
struct node *parent,*location;
if(root==NULL)
{
printf("\ntree is empty");
return;
}
find(item,&parent,&location);
if(location==NULL)
{
printf("\nitem not in tree");
return;
}
if(location->lchild==NULL&&location->rchild==NULL)
case_a(parent,location);
else if(location->lchild!=NULL&&location->rchild==NULL)
case_b(parent,location);
else if(location->lchild==NULL&&location->rchild!=NULL)
case_b(parent,location);
else if(location->lchild!=NULL&&location->rchild!=NULL)
case_c(parent,location);
free(location);
}
void case_a(struct node *par,struct node *loc)
{
if(par==NULL)
root=NULL;
else
{
if(loc==par->lchild)
par->lchild=NULL;
else
par->rchild=NULL;
}
}
void case_b(struct node *par,struct node *loc)
{
struct node *child;
if(loc->lchild!=NULL)
child=loc->lchild;
else
child=loc->rchild;
if(par==NULL)
par->lchild=child;
else
par->rchild=child;
}
void case_c(struct node *par,struct node *loc)
{
struct node *ptr,*ptr1,*suc,*parsuc;
ptr1=loc;
ptr=loc->lchild;
while(ptr->lchild!=NULL)
{
ptr1=ptr;
ptr=ptr->lchild;
}
suc=ptr;
parsuc=ptr1;
if(suc->lchild==NULL&&suc->rchild==NULL)
case_a(parsuc,suc);
else
case_b(parsuc,suc);
if(par==NULL)
root=suc;
else
{
if(loc==par->lchild)
par->lchild=suc;
else
par->rchild=suc;
}
suc->lchild=loc->lchild;
suc->rchild=loc->lchild;
}

No comments:

Post a Comment

There was an error in this gadget