Binary search

// Binary search //

#include
#include
#define NULL 0
struct rec
{
int num;
struct rec *left;
struct rec *right;
};
typedef struct rec node;
node *insert(node *,int);
void search(node *,int);
void preorder(node *);
void inorder(node *);
void postorder(node *);
int select()
{
int selection;
do
{
clrscr();
cout<<"--> MENU <--" << endl;
cout<<"1->Insert a node in BST" << endl;
cout<<"2->Search a node in BST" << endl;
cout<<"3->Preorder traversal of BST" << endl;
cout<<"4->Inorder traversal of BST"<< endl;
cout<<"5->Postorder traversal of BST"<< endl;
cout<<"6->Delete a node in BST"<< endl;
cout<<"Enter ur choice:"; cin>>selection;
if(selection<1||selection>7)
{
cout<<"Invalid choice.\nTryagain.";
getch();
}
}
while(selection<1||selection>7);
return(selection);
}
node *insert(node *tree,int digit)
{
if(tree==NULL)
{
tree=new node;
tree->left=tree->right=NULL;
tree->num=digit;
}
else if(digitnum)
tree->left=insert(tree->left,digit);
else if(digit>tree->num)
tree->right=insert(tree->right,digit);
else {
cout<<"Duplicate node not allowed";
getch();
}
return(tree);
}
void inorder(node *tree)
{ if(tree!=NULL)
{ inorder(tree->left);
cout <<>num;
inorder(tree->right);
}
return;
}
void preorder(node *tree)
{
if(tree!=NULL)
{
cout<<>num;
preorder(tree->left);
preorder(tree->right);
}
return;
}
void postorder(node *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
cout <<>num;
}
return;
}
void search(node *tree,int digit)
{
if(tree==NULL)
{
cout<<"The node doesn't exist"; }
else if(digit==tree->num)
{
cout<<"The node exists:"; }
else if(digitnum)
search(tree->left, digit);
else
search(tree->right, digit);
getch();
return;
}
void locate(node *root,node **par,node **cur,int x,int *found)
{
*found=1;
if(x==root->num)
{
*cur=root;
*found=0;
return;
}
*par=root;
if(xnum)
locate(root->left, &(*par), &(*cur),x,found);
else
locate(root->right, &(*par), &(*cur),x,found);
return;
}
void del(node *tree,int x)
{
node *par,*cur, *xsucc;
int found;
if(tree==NULL)
{
cout<<"Tree is empty (UNDERFLOW)";
getch();
return;
}
locate(tree, &par, &cur,x,&found);
if(found==1)
{
cout<<"Node doesn't exist"; getch(); return;
}
if(cur->left!=NULL && cur->right!=NULL)
{
par=cur;
xsucc=cur->right;
while(xsucc->left!=NULL)
{
par=xsucc;
xsucc=xsucc->left;
}
cur->num=xsucc->num;
cur=xsucc;
}
if(cur->left==NULL && cur->right!=NULL)
{
if(par->left==cur)
par->left=cur->right;
else
par->right=cur->right;
delete cur;
return;
}
if(cur->left!=NULL && cur->right==NULL)
{
if(par->left==cur)
par->left=cur->left;
else
par->right=cur->left;
delete cur;
return;
}
if(cur->left==NULL && cur->right==NULL)
{
if(par->left==cur)
par->left=cur->left;
else
par->right=cur->right;
delete cur;
return;
}
}
int main()
{
node *tree=NULL;
int temp,choice;
do
{
choice=select();
switch(choice)
{
case'1':
cout<<"Enter the value for node:"; cin>>temp;
tree=insert(tree,temp);
break;
case'2':
cout<<"Enter node to search:"; cin>>temp;
search(tree,temp);
break;
case'3':
preorder(tree);
getch();
break;
case'4':
inorder(tree);
getch();
break;
case'5':
postorder(tree);
getch();
break;
case'6':
cout<<"Enter the node to delete:";
cin>>temp;
del(tree,temp);
break;
case'7':
cout<<"Exiting";
break;
}
{
while(choice!=7);
getch();
return(0);
}