My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Binary search
Posted Date: 10 Jun 2008 Resource Type: Articles/Knowledge Sharing Category: Education
|
Posted By: Sanjana Member Level: Gold
Rating:  Points: 1
|
|
|
#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 << endlinorder(tree->right);
}
return;
}
void preorder(node *tree)
{
if(tree!=NULL)
{
cout<< endlpreorder(tree->left);
preorder(tree->right);
}
return;
}
void postorder(node *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
cout << endl}
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);
}
|
Responses
|
No responses found. Be the first to respond and make money from revenue sharing program.
|
|
Watch TV Channels
Watch Asianet TV onlineKairali TV in InternetSurya TV onlineAmritha TV Channel
|