#include<iostream>
using namespace std;
int count=0;
class bst
{private:
struct bstnode
{int element;
bstnode* left;
bstnode* right;
}*root;
public:
bst();
int findmin(bstnode*&t) const;
void insert(int element);
void insertnode(bstnode*&t,int element);
void displayinorder();
void displaypreorder();
void displaypostorder();
void inorder(bstnode*&t);
void preorder(bstnode*&t);
void postorder(bstnode*&t);
void search(int key);
void displayrightlefttopdown();
void rltb(bstnode*&t);
void makeempty(bstnode*&t);
void displayrightleftbottomtop();
void rlbt(bstnode*&t);
void searchnode(bstnode*&t,int key);
void displayreverse();
void reverse(bstnode*&t);
void sizeoftree();
void nodecounter(bstnode*&t);
void remove(int element);
void removenode(bstnode*&t,int element);
~bst();
bool isempty(bstnode*&t);
};
bst::bst()
{root=NULL;
}
void bst::insert(int element)
{insertnode(root,element);}
void bst::insertnode(bstnode*&t,int element)
{if(isempty(t))
{t=new bstnode;
t->element=element;
t->left=NULL;
t->right=NULL;
return;}
if(t->element>element)
insertnode(t->left,element);
if(t->element<element)
insertnode(t->right,element);
else if(t->element==element)
{cout<<"\n element already present insert new element\n";
return;}}
bool bst::isempty(bstnode*&t)
{if(t==NULL)
return true;
else
return false;}
void bst:: search(int key)
{
searchnode(root,key);
}
void bst::searchnode(bstnode*&t,int key)
{if(isempty(root)){cout<<"\n sorry!!!!!!tree is empty"; return;}
if(t==NULL)
return;
else if(t->element==key)
{
cout<<"\n\t\t element found";
return;
}
else if(t->element<key)
{
searchnode(t->right,key);
}
else if(t->element>key)
{
searchnode(t->left,key);
}
}
void bst::displayinorder()
{
inorder(root);
}
void bst::displaypreorder()
{
preorder(root);
}
void bst::displaypostorder()
{
postorder(root);
}
void bst::sizeoftree()
{
nodecounter(root);
}
void bst::nodecounter(bstnode*&t)
{
if(t!=NULL)
{
if(t->left!=NULL)
nodecounter(t->left);
cout<<"->"<<t->element;
count++;
if(t->right!=NULL)
nodecounter(t->right);
}
}
void bst::inorder(bstnode*&t)
{
if(t!=NULL)
{
if(t->left!=NULL)
inorder(t->left);
cout<<"->"<<t->element;
count++;
if(t->right!=NULL)
inorder(t->right);
}
}
void bst::preorder(bstnode*&t)
{
if(t!=NULL)
{cout<<"->"<<t->element;
if(t->left!=NULL)
preorder(t->left);
if(t->right!=NULL)
preorder(t->right);
}
}
void bst::displayrightlefttopdown()
{
rltb(root);
}
void bst::rltb(bstnode*&t)
{
if(t!=NULL)
{cout<<"->"<<t->element;
if(t->right!=NULL)
rltb(t->right);
if(t->left!=NULL)
rltb(t->left);
}}
void bst::postorder(bstnode*&t)
{
if(t!=NULL)
{
if(t->left!=NULL)
postorder(t->left);
if(t->right!=NULL)
postorder(t->right);
cout<<"->"<<t->element;
}
}
void bst::displayrightleftbottomtop()
{
rlbt(root);
}
void bst::rlbt(bstnode*&t)
{
if(t!=NULL)
{
if(t->right!=NULL)
rlbt(t->right);
if(t->left!=NULL)
rlbt(t->left);
cout<<"->"<<t->element;
}
}
void bst::displayreverse()
{
reverse(root);
}
void bst::reverse(bstnode*&t)
{
if(t!=NULL)
{
if(t->right!=NULL)
reverse(t->right);
cout<<"->"<<t->element;
if(t->left!=NULL)
reverse(t->left);
}
}
void bst::remove(int element)
{
removenode(root,element);
}
void bst::removenode(bstnode*&t,int element)
{if(isempty(root))
{
cout<<"\n tree is empty";return;}
if(t==NULL)
return;
else if(t->element>element)
removenode(t->left,element);
else if(t->element<element)
removenode(t->right,element);
else if(t->left!=NULL&&t->right!=NULL)
{
t->element=findmin(t->right);
if(t->element!=-1000)
removenode(t->right,t->element);
}
else
{bstnode*p;
p=t;
t=(t->left!=NULL)?t->left:t->right;
delete p;}
}
int bst::findmin(bstnode*&t) const
{
if(t==NULL)
return -1000;
if(t->left==NULL)
return t->element;
return findmin(t->left);
}
bst::~bst()
{
makeempty(root);
}
void bst::makeempty(bstnode*&t)
{if(t!=NULL)
{
makeempty(t->left);
makeempty(t->right);
delete t;
}
t=NULL;
}
int main()
{
bst bt;
char ch;
int a,b,c,d,f,g,h;
cout<<"\n \t\t*******welcome to binary tree operation******\n-------------------------------------------------------------------------------\n";
do
{cout<<"\n\t\t press 1 to insert node in tree\n\t\t press 2 to inorder display\n\t\t press 3 to preorder display\n\t\t press 4 to postorder display\n\t\t press 5 to search a element in tree\n\t\t press 6 to know the size of tree\n\t\t press 7 to detete a node\n";
cout<<"\t\tpress 8 to display right to left top to bottom\n\t\t press 9 to displayright to left bottom to top\n\t\t press 10 to display in reverse order\n_______________________________________________________________________________";
cout<<"\n enter your choice::\t";
cin>>a;
switch(a)
{
case 1:cout<<"\n enter the element to be added\t\t";
cin>>b;
bt.insert(b);
break;
case 2: cout<<"\n------------------------------------------------------------------\n";
bt.displayinorder();
cout<<"\n---------------------------------------------------------------\n";
break;
case 3: cout<<"\n------------------------------------------------------------------\n";
bt.displaypreorder();
cout<<"\n---------------------------------------------------------------\n";
break;
case 4: cout<<"\n------------------------------------------------------------------\n";
bt.displaypostorder();
cout<<"\n---------------------------------------------------------------\n";
break;
case 5: cout<<"\n enter your element you want to search\t\t";
int c;
cin>>c;
bt.search(c);
break;
case 6:count=0;
bt.sizeoftree();
cout<<"\n size of tree is::\t"<<count;
break;
case 7:
cout<<"\n enter the element you want to delete\t\t";
int d;
cin>>d;
bt.remove(d);
break;
case 8:cout<<"\n------------------------------------------------------------------\n";
bt.displayrightlefttopdown();
cout<<"\n---------------------------------------------------------------\n";
break;
case 9:cout<<"\n------------------------------------------------------------------\n";
bt.displayrightleftbottomtop();
cout<<"\n---------------------------------------------------------------\n";
break;
case 10:cout<<"\n------------------------------------------------------------------\n";
bt.displayreverse();
cout<<"\n---------------------------------------------------------------\n";
break;
default:
cout<<"\n you entered wrong choice:";}
cout<<"\n do you want to continue if yes press y\t\t";
cin>>ch;
}while(ch=='y');
return 0;
}
No comments:
Post a Comment