#include<iostream>
using namespace std;
int found=0;
int size=0;
class binarytree
{private:
struct tnode
{int element;
tnode* left;
tnode*right;
}*root;
public:
binarytree();
void insert(int element);
void insertnode(tnode* &t,int element);
void displayinorder();
void inorder(tnode*&t);
void preorder(tnode*&t);
void displaypreorder();
void displaypostorder();
void postorder(tnode*&t);
void sie(tnode*&t);
void sizeoftree();
bool isempty(tnode*&t);
void search(int key);
void nodefound(tnode*&t,int key);
void removenode(tnode*&t,int key);
void remove(int key);
void removetree(tnode*&t);
~binarytree();
};
binarytree::binarytree()
{root=NULL;}
void binarytree::insert(int element)
{insertnode(root,element);
}
void binarytree::insertnode(tnode* &t,int element)
{if(t==NULL)
{t=new tnode;
t->left=NULL;
t->right=NULL;
t->element=element;
return;}
cout<<"\n you want to insert in left child or right child press 0 for left and 1 for right child\t";
int a;
cin>>a;
if(a==0)
insertnode(t->left,element);
else if(a==1)
insertnode(t->right,element);
else cout<<"\n you inserted wrong input";
return;
}
bool binarytree::isempty(tnode*&t)
{
if(t==NULL)
return true;
else
return false;}
void binarytree::displayinorder()
{if(isempty(root))
{
cout<<"\n sorry!!! tree is empty";
return;
}
inorder(root);}
void binarytree::displaypreorder()
{if(isempty(root))
{
cout<<"\n sorry!!! tree is empty";
return;
}
preorder(root);}
void binarytree::displaypostorder()
{if(isempty(root))
{
cout<<"\n sorry!!! tree is empty";
return;
}
postorder(root);}
void binarytree::inorder(tnode*& t)
{if(t!=NULL){
if(t->left!=NULL)
inorder(t->left);
cout<<"->"<<t->element;
if(t->right!=NULL)
inorder(t->right);
}}
void binarytree::preorder(tnode*& t)
{if(t!=NULL){
cout<<"->"<<t->element;
size++;
if(t->left!=NULL)
preorder(t->left);
if(t->right!=NULL)
preorder(t->right);
}}
void binarytree::sizeoftree()
{
sie(root);
}
void binarytree::sie(tnode*&t)
{if(t!=NULL){
size++;
if(t->left!=NULL)
sie(t->left);
if(t->right!=NULL)
sie(t->right);
}}
void binarytree::postorder(tnode*& t)
{if(t!=NULL){
if(t->left!=NULL)
postorder(t->left);
if(t->right!=NULL)
postorder(t->right);
cout<<"->"<<t->element;
}}
void binarytree::search(int key)
{
nodefound(root,key);
if(found==0)
{
cout<<"\n element not present\n";
}
}
void binarytree::nodefound(tnode*&t,int key)
{if(t!=NULL)
{
if(t->element==key){
cout<<"\n element found";
found=1;
return ;}
if(t->left!=NULL)
nodefound(t->left,key);
if(t->right!=NULL)
nodefound(t->right,key);
}
//cout<<"\n element not found\n";
}
void binarytree::remove(int key)
{
removenode(root,key);
}
void binarytree::removenode(tnode*&t,int key)
{if(isempty(root))
{cout<<"\n tree is empty\n";
return;
}
if(t->element==key)
{
if(t->left!=NULL&&t->right!=NULL)
{
t->element=t->left->element;
removenode(t->left,t->element);
}
/*else if(t->left==NULL&&t->right!=NULL){
while(t->right->right!=NULL)
{t->element=t->right->element;
t=t->right;}
t->element=t->right->element;
tnode*s=t->right;
t->right=NULL;
delete(s); return;}*/
else {tnode*p;
p=t;
t=(t->left!=NULL)?t->left:t->right;
delete p; return;}
}
if(t->left!=NULL)
removenode(t->left,key);
if(t->right!=NULL)
removenode(t->right,key);
}
binarytree::~binarytree()
{if(isempty(root))
return;
removetree(root);
}
void binarytree::removetree(tnode*&t){
if(t!=NULL){
if(t->left!=NULL)
removetree(t->left);
delete(t);
if(t->right!=NULL)
removetree(t->right);
}t=NULL;}
int main()
{
binarytree 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<<"_______________________________________________________________________________";
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:size=0;
bt.sizeoftree();
cout<<"\n size of tree is::\t"<<size;
break;
case 7:
cout<<"\n enter the element you want to delete\t\t";
int d;
cin>>d;
bt.remove(d);
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