Binary Search Tree

//Program to illustarte Binary Search Tree
#include
#include

#define FALSE 0
#define TRUE 1

struct node
{
int data;
node *lchild;
node *rchild;
};


class btree
{
node *root;

public:
btree()
{
root=NULL;
}

void build_tree(int);
void insert(node**,int);
void inorder(node *);
void search(node **,int,node **, node**,int *);
void delet(int);
void remove(node **,int);
void traverse(int);
void disp();



};

void btree::insert(node **sr,int num)
{
if(*sr==NULL)
{
*sr=new node;
(*sr)->data=num;
(*sr)->lchild=(*sr)->rchild=NULL;
}
else
{
//if data less traverse list
if(num==(*sr)->data)
{
cout<<"\nCannot insert.\n";
return;
}
if(num<(*sr)->data)
insert(&(*sr)->lchild,num);
else
insert(&(*sr)->rchild,num);
}
}


void btree::build_tree(int num)
{
insert(&root,num);
}


void btree::delet(int num)
{
remove(&root,num);

}


void btree::traverse(int num)
{

int found;
node *parent,*x;


if(root==NULL)
{
cout<<"\nTree empty.\n\n";
return;
}

parent=x=NULL;

search(&root,num,&parent,&x,&found);

if(found==TRUE)
cout<<"\nNode Found.\n\n";
else
cout<<"\nNode not found.\n\n";



}


void btree::remove(node **sr,int num)
{
int found;
node *parent,*x,*xsucc;

if(*sr==NULL)
{
cout<<"\nTree empty .Deletion not possible.\n\n";
return;
}

parent=x=NULL;

search(&root,num,&parent,&x,&found);

if(found==FALSE)
{
cout<<"\nElement not found.\n\n";
return;
}

else
{
//the node to be deleted has two children
if(x->lchild!=NULL&&x->rchild!=NULL)
{
parent=x;
xsucc=x->rchild;

while(xsucc->lchild!=NULL)
{
parent=xsucc;
xsucc=xsucc->lchild;

}

x->data=xsucc->data;
x=xsucc;
}


//if the node has only left child

if(x->lchild!=NULL&&x->rchild==NULL)
{
if(parent->lchild==x)
parent->lchild=x->lchild;
else
parent->rchild=x->lchild;
delete x;
return;
}

//if the node has only right child



if(x->rchild!=NULL&&x->lchild==NULL)
{
if(parent->lchild==x)
parent->lchild=x->rchild;
else
parent->rchild=x->rchild;
delete x;
return;
}


//if the node to be deleted has no child

if(x->lchild==NULL&&x->rchild==NULL)
{
if(parent->rchild==x)
parent->rchild=NULL;
else
parent->lchild=NULL;
delete x;
return;
}

}
}


void btree::search(node **sr,int num,node **par,node **x,int *found)
{
node *q;
q=*sr;
*found=FALSE;
*par=NULL;

while(q!=NULL)
{
//if the node to be deleted is found
if(q->data==num)
{
*found=TRUE;
*x=q;
return;
}
*par=q;
if(q->data>num)
q=q->lchild;
else
q=q->rchild;

}
}

void btree::inorder(node *sr)
{ if(sr!=NULL)
{
inorder(sr->lchild);
cout<data<<"\t";
inorder(sr->rchild);

}
}



void btree::disp()
{
if(root==NULL)
cout<<"\nTree empty!!\n";
inorder(root);

}

void main()
{

clrscr();
int num,ch;
char opt;
btree bt;

cout<<"\n\tBINARY SEARCH TREE OPERATIONS\n\t-------------------------------\n\n";

do
{
cout<<"\n\n1.INSERT\n2.DELETE\n3.TRAVERSE\n4.DISPLAY\n";
cout<<"\nEnter the choice:";
cin>>ch;

switch(ch)
{
case 1:

cout<<"\nEnter the data:";
cin>>num;
bt.build_tree(num);
break;

case 2:

cout<<"\nEnter the data:";
cin>>num;
bt.delet(num);
break;


case 3: cout<<"\nEnter the data:";
cin>>num;
bt.traverse(num);
break;

case 4:
bt.disp();
break;
default:
cout<<"\nInvalid Option!!!\n";
break;

}

cout<<"\nDo u want to continue?";
cin>>opt;
}while(opt=='y'||opt=='Y');

getch();

}