Binary Search Tree

BINARY SEARCH TREE

#include “stdio.h”
#include “conio.h”
#include
#define NULL 0
struct node
{
int data;
struct node *lchild,*rchild,*btree,*temp;
};
struct node *getnode();
void view(struct node*,int);
struct node *cbtree();
struct node *inode(struct node *btree,struct node *temp);
struct node *dnode(int,struct node*);
struct node *search(struct node*,int);
struct node *btree=NULL,*temp,*newnode;
void display(void);
char ch;
void main()
{
int choice,key;
clrscr();
display();
while(choice!=6)
{
printf("\nEnter ur choice:\n");
scanf("%d",&choice);
switch(choice)
{
case 0:
display();
break;
case 1:
btree=NULL;
printf("\nCreate a new Binary Tree\n");
btree=cbtree();
break;
case 2:
printf("\nInsert the Node\n");
temp=getnode();
btree=inode(btree,temp);
break;
case 3:
if(btree==NULL)
printf("\nBinary tree is Empty\n");
else
{
printf("\nDelete the node\n");
printf("Enter the element to delete:");
scanf("%d",&key);
btree=dnode(key,btree);
}
break;
case 4:
if(btree==NULL)
printf("\nBinary tree is Empty\n");
else
{
printf("\nSearch the node\n");
printf("\nEnter the search element:\n");
scanf("%d",&key);
temp=search(btree,key);
if(temp==NULL)
printf("\nSearch element %d is not found\n",key);
else
printf("\nSearch element %d is found",key);
}
break;
case 5:
if(btree!=NULL)
{
printf("\nBinary search tree is:\n");
view(btree,1);
}
else
printf("\nBinary tree is empty\n");
break;
case 6:
exit(0);
break;
default:
printf("\nEnter the correct choice");
free(btree);
break;
}
}
}

void display()
{
printf("\nBasic Operations in a Binary search Tree");
printf("\n\t0.ShowMenu");
printf("\n\t1.Create a Binary Tree");
printf("\n\t2.Insert a Node");
printf("\n\t3.Delete a Node");
printf("\n\t4.Search a Node");
printf("\n\t5.View the Btree");
printf("\n\t6.Exit");
}
struct node *getnode()
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the data:");
scanf("%d",&newnode->data);
newnode->lchild=NULL;
newnode->rchild=NULL;
return(newnode);
}
struct node *cbtree()
{
do
{
temp=getnode();
btree=inode(btree,temp);
fflush(stdin);
printf("\nDo you wish to add data(y/n):");
scanf("%c",&ch);
}while((ch=='y')(ch=='Y'));
return(btree);
}
struct node *inode(struct node *btree,struct node *temp)
{
if(btree==NULL)
return temp;
else if(temp->data <>data)
btree->lchild=inode(btree->lchild,temp);
else if(temp->data > btree->data)
btree->rchild=inode(btree->rchild,temp);
else if(temp->data==btree->data)
{
printf("\nData Aleady Exists\n");
return(btree);
}
return(btree);
}
struct node *dnode(int key,struct node *btree)
{
struct node *p,*fop,*suc,*fosuc;
p=btree;
fop=NULL;
while(p!=NULL && p->data!=key)
{
fop=p;
p=(key <>data)? p->lchild : p->rchild;
}
if(p==NULL)
{
printf("\nElement not found\n");
return(btree);
}
if(p->lchild!=NULL && p->rchild!=NULL)
{
for(fosuc=p,suc=p->rchild;suc->lchild!=NULL;suc=suc->lchild)
fosuc=suc;
if(suc->rchild==NULL)
{
if(fosuc->rchild==suc)
fosuc->rchild=NULL;
else if(fosuc->lchild==suc)
fosuc->lchild=NULL;
}
else if(suc->rchild!=NULL)
{
if(fosuc->rchild==suc)
fosuc->rchild=suc->rchild;
else if(fosuc->lchild==suc)
fosuc->lchild=suc->rchild;
}
suc->lchild=p->lchild;
suc->rchild=p->rchild;
if(fop==NULL)
return(suc);
if(fop->lchild==p)
fop->lchild=suc;
else if(fop->rchild==p)
fop->rchild=suc;
return(btree);
}
else if(p->lchild==NULL && p->rchild==NULL)
{
if(fop==NULL)
return(NULL);
else if(fop->rchild==p)
fop->rchild=NULL;
else if(fop->lchild==p)
fop->lchild=NULL;
}
else if((p->lchild!=NULL && p->rchild==NULL)
(p->lchild==NULL && p->rchild!=NULL))
{
if(fop==NULL)
return((p->rchild!=NULL)?p->rchild:p->lchild);
else if(fop->rchild==p)
fop->rchild=(p->rchild!=NULL)?p->rchild:p->lchild;
else if(fop->lchild==p)
fop->lchild=(p->rchild!=NULL)?p->rchild:p->lchild;
}
free(p);
return(btree);
}
struct node *search(struct node *btree,int key)
{
if(btree==NULL)
return NULL;
else if(key>btree->data)
return search(btree->rchild,key);
else if(keydata)
return search(btree->lchild,key);
else if(key==btree->data)
return(btree);
return(btree);
}
void view(struct node *btree,int level)
{
int k;
if(btree==NULL)
return;
view(btree->rchild,level+1);
printf("\n");
for(k=0;kdata);
view(btree->lchild,level+1);
}
Output will be
Basic Operations in a Binary search Tree
0.ShowMenu
1.Create a Binary Tree
2.Insert a Node
3.Delete a Node
4.Search a Node
5.View the Btree
6.Exit
Enter ur choice:1

Create a new Binary Tree

Enter the data:5

Do you wish to add data(y/n):Y

Enter the data:2

Do you wish to add data(y/n):Y

Enter the data: 9

Do you wish to add data(y/n):Y

Enter the data:3

Do you wish to add data(y/n):Y

Enter the data:12

Do you wish to add data(y/n):N

Enter ur choice:5

Binary search tree is:

12
9
5
3
2
Enter ur choice:2

Insert the Node

Enter the data: 6

Enter ur choice:5

Binary search tree is:

12
9
6
5
3
2
Enter ur choice: 3

Delete the node

Enter the element to delete: 9

Enter ur choice: 4

Search the node

Enter the search element: 6

Search element 6 is found

Enter ur choice:6