EX.NO:6 IMPLEMENTATION OF BINARY SEARCH TREE
AIM:
To write a C- program to implement binary search tree.
ALGORITHM:
Step 1. Start the program.
Step 2. INSERT:
*Get the value to be inserted
*In insertion if the key value is larger than root node, it is inserted as
right child.
*If the key value is smaller than the root node, then it is inserted as left
child.
Step 3. SEARCH:
*Get the value to be searched.
*Check for the tree is null or not if it is null then return NULL.
*If the tree is not empty, then perform search
*If the key value is less than the root of tree, search the element at the
left sub tree.
*If the key value is greater than the root, search the element at the right
sub tree.
Step 4. DELETE:
*Get the value to be deleted.
*In deletion check that the node is a leaf or not ,if the node is a leaf
delete it immediately.
*If the node has one child, the node is deleted by adjusting the parents
*If the node has two child, the general strategy is to replace the data
of this node with the smallest data of right sub tree and recursively
delete that node.
Step 5.DISPLAY:
In display, display the value of the in order traversals.
Step 6:Stop the program.
PROGRAM:
#include<stdio.h>
#include<conio.h>
typedef struct node
{
int e;
struct node *l;
struct node *r;
}*btree;
btree bst;
btree findmin(btree a)
{
if(a==NULL)
return NULL;
else if(a->l==NULL)
return a;
else
return findmin(a->l);
}
btree insert(int x,btree a)
{
static int flag=0,parent;
if(a==NULL)
{
a=(btree)malloc(sizeof(struct node));
a->e=x;
printf("\n %d is inserted as ",x);
switch(flag)
{
case 0:
printf("root node\n");
break;
case 1:
printf("right child of %d\n",parent);
break;
case 2:
printf("left child of %d\n",parent);
}
flag=0;
a->l=a->r=NULL;
}
else if(x<a->e)
{
flag=2;
parent=a->e;
a->l=insert(x,a->l);
}
else if(x>a->e)
{
flag=1;
parent=a->e;
a->r=insert(x,a->r);
}
else if(x==a->e)
printf("\n duplicate element\n");
return a;
}
btree delet(int x,btree a)
{
static int flag=0,parent;
btree tmp;
if(!a)
printf("\nelement not found");
else
{
if(x<a->e)
{
parent=a->e;
flag=2;
a->l=delet(x,a->l);
}
else if(x>a->e)
{
parent=a->e;
flag=1;
a->r=delet(x,a->r);
}
else
{
if(a->l&&a->r)
{
tmp=findmin(a->r);
a->e=tmp->e;
printf("\n %d is assigned as",a->e);
switch(flag)
{
case 0:
printf("root node\n");
break;
case 1:
printf("right child of %d\n",parent);
break;
case 2:
printf("left child of %d\n",parent);
}
flag=0;
a->r=delet(a->e,a->r);
}
else
{
tmp=a;
if(a->l==NULL)
a=a->r;
else if(a->r==NULL)
a=a->l;
if(a!=NULL)
{
printf("\n %d is assigned as",a->e);
switch(flag)
{
case 0:
printf("root node\n");
break;
case 1:
printf("right child of %d\n",parent);
break;
case 2:
printf("left child of %d\n",parent);
}
}
flag=0;
free(tmp);
}
}
}
return a;
}
void display(btree a)
{
if(a!=NULL)
{
display(a->l);
printf("%d",a->e);
printf("\t");
display(a->r);
}
}
void main()
{
int i,n,value,ch;
clrscr();
printf("\n creation....\n enter the no of nodes");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n enter the value to be inserted");
scanf("%d",&value);
bst=insert(value,bst);
}
do
{
printf("\nmenu\n1.insert\n2.delete\n3.display in order\n4.exit\nwhat do you?");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter the value to be inserted:");
scanf("%d",&value);
bst=insert(value,bst);
break;
case 2:
printf("enter the value to be deleted:");
scanf("%d",&value);
bst=delet(value,bst);
break;
case 3:
if(bst)printf("\n root is %d \n",bst->e);
else printf("\n no tree created");
display(bst);
}
}
while(ch!=4);
getch();
}
