#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
node* left;
int val;
node* right;
};
node* root=NULL;
class BST
{
public:
node* insert(node*,int);
node* del(node*,int);
bool search(node*,int);
node* successor(node*);
void preorder(node*);
void postorder(node*);
void inorder(node*);
};
node* BST::insert(node* t,int ele)
{
node* p;
p=new node;
if(t==NULL)
{
p->val=ele;
p->right=p->left=NULL;
t=p;
}
else if(ele<t->val)
t->left=insert(t->left,ele);
else if(ele>t->val)
t->right=insert(t->right,ele);
return t;
}
node* BST::del(node* t,int ele)
{
node* tmp;
if(t==NULL)
{
cout<<"BST is empty.";
return NULL;
}
else if(ele>t->val)
t->right=del(t->right,ele);
else if(ele<t->val)
t->left=del(t->left,ele);
else if(t->left!=NULL&&t->right!=NULL)
{
tmp=successor(t->left);
t->val=tmp->val;
t->left=del(t->left,t->val);
}
else
{
tmp=t;
if(t->right==NULL)
t=t->left;
else if(t->left==NULL)
t=t->right;
free(tmp);
}
return t;
}
node* BST::successor(node* t)
{
while(t->right!=NULL)
t=t->right;
return t;
}
bool BST::search(node* p,int ele)
{
bool b;
if(p==NULL)
return false;
else if(ele==p->val)
return true;
else if(ele>p->val)
b=search(p->right,ele);
else if(ele<p->val)
b=search(p->left,ele);
return b;
}
void BST::preorder(node* t)
{
if(t!=NULL)
{
cout<<t->val<<"\t";
if(t->left!=NULL)
preorder(t->left);
if(t->right!=NULL)
preorder(t->right);
}
}
void BST::postorder(node* t)
{
if(t!=NULL)
{
if(t->left!=NULL)
postorder(t->left);
if(t->right!=NULL)
postorder(t->right);
cout<<t->val<<"\t";
}
}
void BST::inorder(node* t)
{
if(t!=NULL)
{
if(t->left!=NULL)
inorder(t->left);
cout<<t->val<<"\t";
if(t->right!=NULL)
inorder(t->right);
}
}
int main()
{
BST ob;
int option,ele;
bool b;
while(1)
{
cout<<"\n1.Insert\n2.Delete\n3.Search\n4.Display in Pre Order\n5.Display in Post Order\n6.Display In Order\n7.Exit Program\n";
cout<<"\nEnter your option:";
cin>>option;
switch(option)
{
case 1:
{
cout<<"Enter the element to be inserted:";
cin>>ele;
root=ob.insert(root,ele);
}
break;
case 2:
{
cout<<"Enter the node to be deleted:";
cin>>ele;
root=ob.del(root,ele);
}
break;
case 3:
{
cout<<"Enter the element to be searched:";
cin>>ele;
b=ob.search(root,ele);
if(b==true)
cout<<"Element found.";
else
cout<<"Element not found.";
}
break;
case 4:ob.preorder(root);
break;
case 5:ob.postorder(root);
break;
case 6:ob.inorder(root);
break;
case 7:exit(1);
}
}
}
No comments:
Post a Comment