C program to implement Binary Search Tree

0
577

C program to implement Binary Search Tree

CONSTRUCTION:

  1. Start the program.
  2. Read the option value
  3. If option=1 then read x

And check if root is Null then assign root as t

  1. Else store current data as x and print it

If (curr->data=x) then assign left child to curr

and check if(curr=null) Prev->lchild=t

  1. Else Prev=curr, curr=curr->rchild then check if(curr==Null)then pre-> rchild=t
  2. Print the value of x
  3. Enter the no of deleted x

Check p is not null and then assign lchild as p

  1. If p is null then print x

Check P as root then assign c as root. Then delete the node p

  1. Stop the program.

PROGRAM :

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *left,*right;
}
tree;
tree *getnode();
void displaymenu();
void readnode(tree*);
void releasenode(tree* head);
tree *createbtree();
tree *insertnode(tree *btree,tree *temp);
tree *deletenode(int digit,tree *btree);
tree *searchnode(tree *btree,int key);
void view(tree *btree,int level);
tree *findparnode(tree *btree,int item,tree **par);
tree *delnochild(tree *btree,tree *par,tree *loc);
tree *del1child(tree *btree,tree *par,tree *loc);
tree *del2child(tree *btree,tree *par,tree *loc);
void main()
{
int choice,key;
tree *btree=NULL,*temp,*par,*loc;
displaymenu();
while(1)
{
printf("\n????");
scanf("%d",&choice);
switch(choice)
{
case 0:
displaymenu();
break;
case 1:
btree=NULL;
printf("\nCreate New Binary Search Tree");
btree=createbtree();
break;
case 2:
printf("\n Insert the node in the tree");
temp=getnode();
readnode(temp);
btree=insertnode(btree,temp);
break;
case 3:
if(btree==NULL)
printf("Binary search tree is empty.");
else
{
printf("\nDelete the node from the tree");
printf("\nEnter the element for deleting the node:");
scanf("%d",&key);
btree=deletenode(key,btree);
}
break;
case 4:
if(btree==NULL)
printf("\nBinary search tree is empty");
else
{
printf("\n Search the node in the tree");
printf("\n Enter the searching element");
scanf("%d",&key);
if(temp==NULL)
printf("\nSearch element %d is not found",key);
else
printf("\nSearch element %d is found",temp->data);
}
break;
case 5:
if(btree==NULL)
printf("\nBinary search tree is empty");
else
{
printf("\n Binary search tree is....\n");
view(btree,1);
}
break;
default:
printf("\nEnd of run of UR program");
releasenode(btree);
exit(0);
}
}
}
void displaymenu()
{
printf("\nBasic Operations in Binary Tree....");
printf("\n\t0.Show menu\n\t1.Create Binary Search Tree\n\t2.Insert a node");
printf("\n\t3.Delete a node\n\t4.Search a node\n\t5.View the binary tree");
printf("\n\t6.Exit");
}
tree *getnode()
{
int size;
tree *newnode;
size=sizeof(tree);
newnode=(tree*)malloc(size);
return(newnode);
}
void readnode(tree* newnode)
{
printf("\nEnter the data:");
scanf("%d",&newnode->data);
newnode->left=NULL;
newnode->right=NULL;
}
void releasenode(tree* head)
{
free(head);
}
tree *createbtree()
{
char ch;
tree *btree=NULL,*temp;
do
{
temp=getnode();
readnode(temp);
btree=insertnode(btree,temp);
fflush(stdin);
printf("\nDo U wish to add data in the tree (y/n)??");
scanf("%c",&ch);
}
while((ch=='y')||(ch=='Y'));
return btree;
}
tree *findparnode(tree *btree,int data,tree **par)
{
if(btree==NULL)
return NULL;
else if(data<btree->data)
{
*par=btree;
return findparnode(btree->left,data,par);
}
else if(data>btree->data)
{
*par=btree;
return findparnode(btree->right,data,par);
}
else if(data==btree->data)
return btree;
}
tree *insertnode(tree *btree,tree *temp)
{
tree *par=NULL,*loc=NULL;
loc=findparnode(btree,temp->data,&par);
if(loc!=NULL)
{
printf("\nData is already existing....");
return btree;
}
if(btree==NULL)
return temp;
else if(temp->data<par->data)
par->left=temp;
else
par->right=temp;
return btree;
}
tree *deletenode(int key,tree *btree)
{
tree *par=NULL,*loc=NULL;
loc=findparnode(btree,key,&par);
if(loc==NULL)
{
printf("\n Item not Present");
return btree;
}
if(loc->left==NULL&&loc->right==NULL)
btree=delnochild(btree,par,loc);
if((loc->left!=NULL&&loc->right==NULL)||(loc->left==NULL&&loc->right!=NULL))
btree=del1child(btree,par,loc);
if(loc->left!=NULL&&loc->right!=NULL)
btree=del2child(btree,par,loc);
releasenode(loc);
return btree;
}
tree *delnochild(tree *btree,tree *par,tree *loc)
{
if(par==NULL)
return NULL;
else if(loc==par->left)
par->left=NULL;
else if(loc==par->right)
par->right=NULL;
return btree;
}
tree *del1child(tree *btree,tree *par,tree *loc)
{
tree *temp;
if(loc->left!=NULL)
temp=loc->left;
else
temp=loc->right;
if(par==NULL)
btree=temp;
else if(loc==par->left)
par->left=temp;
else if(loc==par->right)
par->right=temp;
return btree;
}
tree *del2child(tree *btree,tree *par,tree *loc)
{
tree *suc,*parsuc;
parsuc=loc;
for(suc=loc->right;suc->left!=NULL;suc=suc->left)
parsuc=suc;
if(suc->left==NULL&&suc->right==NULL)
delnochild(btree,parsuc,suc);
else
del1child(btree,parsuc,suc);
if(par==NULL)
btree=suc;
else if(loc==par->left)
par->left=suc;
else if(loc==par->right)
par->right=suc;
suc->left=loc->left;
suc->right=loc->right;
return btree;
}
tree *searchnode(tree *btree,int key)
{
if(btree==NULL)
return NULL;
else if(key<btree->data)
return searchnode(btree->left,key);
else if(key>btree->data)
return searchnode(btree->right,key);
else if(key==btree->data)
return btree;
}
void view(tree *btree,int level)
{
int k;
if(btree==NULL)
return;
view(btree->right,level+1);
printf("\n");
for(k=0;k<level;k++)
printf(" ");
printf("%d",btree->data);
view(btree->left,level+1);
}

Leave a Reply