IMPLEMENT BINARY SEARCH TREE
ALGORITHM:-
Step 1: Start the process.
Step 2: Initialize and declare variables.
Step 3: Construct the Tree
Step 4: Data values are given which we call a key and a binary search tree
Step 5: To search for the key in the given binary search tree, start with the root node and Compare the key with the data value of the root node. If they match, return the root pointer.
Step 6: If the key is less than the data value of the root node, repeat the process by using the leftsubtree.
Step 7: Otherwise, repeat the same process with the right subtree until either a match is found or the subtree under consideration becomes an empty tree.
Step 8: Terminate
PROGRAM
#include<iostream.h
#include<conio.h
#include<stdlib.h
#include<process.h
typedefstructbtree
{
int data;
structbtree*left;
structbtree*right;
}*node;
nodefindmin(node t)
{
if(t->left==NULL)
{
return(t);
}
else
{
return(findmin(t->left));
}
}
node insert(node t,int x)
{
if(t==NULL)
{
t=(structbtree*)malloc(sizeof(structbtree));
if(t!=NULL)
{
t->data=x;
t->left=NULL;
t->right=NULL;
}
}
else if(t->data>x)
{
t->left=insert(t->left,x);
}
else if(t->data<x)
{
t->right=insert(t->right,x);
}
return t;
}
node deletion(node t,int x)
{
if(t==NULL)
{
printf(“\nEmpty");
}
else if(x>t->data)
{
t->right=deletion(t->right,x);
}
else if(x<t->data)
{
t->left=deletion(t->left,x);
}
else if(t->right!=NULL&t->left!=NULL)
{
node temp;
temp=findmin(t->right);
t->data=temp->data;
t->right=deletion(t->right,t->data);
}
else
{
node temp;
temp=t;
if(t->left==NULL)
{
t=t->right;
}
else if(t->right==NULL)
{
t=t->left;
}
free(temp);
}
return t;
}
nodefindmax(node t)
{
if(t->right==NULL)
{
return t;
}
else
{
return(findmax(t->right));
}
}
voidinorder(node t)
{
if(t!=NULL)
{
inorder(t->left);
cout<"\t"<t->data;
inorder(t->right);
}
}
void main()
{
intch,a;
node t,t1,t2;
t=NULL;
clrscr();
while(1)
{
printf(“\n Binary search tree");
printf(“\n 1.insert\n2.delete\n3.find minimum\n4.find maximum\n5.display tree\n6.exit)";
printf(“\n Enter your choice");
scanf(“%d”,&ch);
switch(ch)
{
case 1:printf(“\nEnter the data to be inserted");
scanf(“%d”,&a);
t=insert(t,a);
break;
case 2:printf(“\nEnter the data to be deleted";
scanf(“%d”,&a);
t=deletion(t,a);
break;
case 3:t1=findmin(t);
printf(“\n%dis the minimum element",t1->data);
break;
case 4:t2=findmax(t);
printf(“\n %d is the maximum element",t2->data);
break;
case 5:inorder(t);
break;
case 6:exit(0);
break;
default:printf(“\n Wrong input");
}
}
}