Binary Search Tree


A complete working program of binary search tree.

#include<stdio.h>
#include<conio.h>
#define null 0
struct tree
{
int info;
struct tree*lchild;
struct tree*rchild;
};

struct tree* Insert(struct tree *root,int x)
{
struct tree*newnode,*p,*q;
newnode=(struct tree*)malloc(sizeof(struct tree));
newnode->info=x;
newnode->lchild=null;
newnode->rchild=null;
p=root;
q=p;
while(p!=null&&q->info!=x)
{
q=p;
if(p->info>x)
p=p->lchild;
else
p=p->rchild;
}
if(q->info>x)
q->lchild=newnode;
else if(q->info<x)
q->rchild=newnode;
else if(q->info==x)
printf(“duplicate”);
return root;
}
struct tree* Delete(struct tree*root,int x)
{
struct tree*prev,*node,*p,*temp;
p=root;
while(p->info!=x&&p!=null)
{
prev=p;
if(p->info>x)
p=p->lchild;
else
p=p->rchild;
}
if(p->info==x)
{
if(p->lchild==null)
node=p->rchild;
else if(p->rchild==null)
node=p->lchild;
else
{
node=p->lchild;
temp=node;
while(temp->rchild!=null)
{
temp=temp->rchild;
temp->rchild=p->rchild;
}
if(p==root)
root=node;
else if(prev->lchild==p)
prev->lchild=node;
else if(prev->rchild==p)
prev->rchild=node;
free(p);
}
}
return root;
}
void Pre_order(struct tree*p)
{
if(p!=null)
{
printf(“%d”,p->info);
Pre_order(p->lchild);
Pre_order(p->rchild);
}
getch();
}
void main()
{
struct tree *root=null,*p,*q,*newnode,*temp;
int n,x,count,choice;
clrscr();
printf(“enter no of nodes\n”);
scanf(“%d”,&n);
printf(“enter the values\n”);
scanf(“%d”,&x);
root=(struct tree*)malloc(sizeof(struct tree));
root->info=x;
root->lchild=null;
root->rchild=null;
count=1;
while(count<n)
{
printf(“enter a value\n”);
scanf(“%d”,&x);
newnode=(struct tree*)malloc(sizeof(struct tree));
newnode->info=x;
newnode->lchild=null;
newnode->rchild=null;
p=root;
q=p;
while(p!=null&&q->info!=x)
{
q=p;
if(p->info>x)
p=p->lchild;
else
p=p->rchild;
if(q->info>x)
q->lchild=newnode;
else if(q->info<x)
q->rchild=newnode;
else if(q->info==x)
printf(“duplicate”);

}
count++;
}
do
{
printf(“\n1.Insert\n2.Delete\n3.Pre_order\n4.exit\n”);
printf(“enter your choice\n”);
scanf(“%d”,&choice);
switch(choice)
{
case 1: printf(“enter the element to be inserted\n”);
scanf(“%d”,&x);
root=Insert(root,x);
break;
case 2: printf(“enter the element to be deleted\n”);
scanf(“%d”,&x);
root=Delete(root,x);
break;
case 3: Pre_order(p);
break;
case 4: break;
default:printf(“invalid choice\n”);
}
}while(choice!=4);
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s