#include<iostream>
using namespace std;
class avl
{private:
struct avlnode
{int element;
int height;
avlnode* left;
avlnode* right;
avlnode(const int&element,avlnode* left,avlnode*right,int h=0):element(element),left(left),right(right),height(h){}
}*root;
public:
avl();
~avl();
void insert(int element);
void insertnode(avlnode* &t,int element);
void displayinorder();
void inorder (avlnode* &t);
void displaypreorder();
void preorder (avlnode* &t);
void displaypostorder();
void postorder (avlnode* &t);
void search(int element);
void searchnode(avlnode*&t,int element);
int height(avlnode*&t);
void rotatewithleftchild(avlnode* &t);
void rotatewithrightchild(avlnode* &t);
void doublerotatewithleftchild(avlnode* &t);
void doublerotatewithrightchild(avlnode* &t);
int max(int x,int y);
void remove(int element);
void removenode(avlnode*&t,int element);
int findmin(avlnode*&t);
void makeempty(avlnode*&t);
};
avl::avl()
{root=NULL;
}
avl::~avl()
{makeempty(root);}
void avl::makeempty(avlnode*&t)
{if(t!=NULL)
{
makeempty(t->left);
makeempty(t->right);
delete t;
}
t=NULL;
}
int avl::findmin(avlnode*&t)
{
if(t==NULL)
return -1000;
if(t->left==NULL)
return t->element;
return findmin(t->left);
}
void avl::insert(int element)
{insertnode(root,element);}
void avl::insertnode(avlnode*& t,int element)
{if(t==NULL)
{t=new avlnode(element,NULL,NULL);
return;}
else if(t->element>element)
{
insertnode(t->left,element);
if(height(t->left)-height(t->right)==2)
if(element<t->left->element)
rotatewithleftchild(t);
else
doublerotatewithleftchild(t);
}
else if(t->element<element)
{
insertnode(t->right,element);
if(height(t->right)-height(t->left)==2)
if(t->right->element<element)
rotatewithrightchild(t);
else
doublerotatewithrightchild(t);}
else ;
t->height=max(height(t->left),height(t->right))+1;
}
int avl::max(int x,int y)
{if(x>=y)
return x;
else
return y;
}
int avl::height(avlnode*&t)
{
return t==NULL?-1:t->height;
}
void avl::doublerotatewithrightchild(avlnode*&t)
{rotatewithleftchild(t->right);
rotatewithrightchild(t);
}
void avl::doublerotatewithleftchild(avlnode*&t)
{rotatewithrightchild(t->left);
rotatewithleftchild(t);
}
void avl::rotatewithleftchild(avlnode*&t)
{avlnode* p=t->left;
t->left=p->right;
p->right=t;
t->height=max(height(t->left),height(t->right))+1;
p->height=max(height(p->left),height(p->right))+1;
t=p;
}
void avl::rotatewithrightchild(avlnode*&t)
{
avlnode* p=t->right;
t->right=p->left;
p->left=t;
t->height=max(height(t->left),height(t->right))+1;
p->height=max(height(p->left),height(p->right))+1;
t=p;
}
void avl::displayinorder()
{
inorder(root);
}
void avl::displaypreorder()
{
preorder(root);
}
void avl::displaypostorder()
{
postorder(root);
}
void avl::inorder(avlnode*&t)
{
if(t!=NULL)
{
if(t->left!=NULL)
inorder(t->left);
cout<<"(---)"<<t->element;
if(t->right!=NULL)
inorder(t->right);
}
}
void avl::preorder(avlnode*&t)
{
if(t!=NULL)
{cout<<"(---)"<<t->element;
if(t->left!=NULL)
preorder(t->left);
if(t->right!=NULL)
preorder(t->right);
}
}
void avl::postorder(avlnode*&t)
{
if(t!=NULL)
{
if(t->left!=NULL)
postorder(t->left);
if(t->right!=NULL)
postorder(t->right);
cout<<"(---)"<<t->element;
}
}
void avl::search(int element)
{
searchnode(root,element);
}
void avl::searchnode(avlnode*&t,int key)
{
if(t==NULL)
{
cout<<"\nsorry!!!! element not present";
return;
}
else if(t->element==key)
{
cout<<"\n\t\t element found"<<"\tat\t"<<t->height;
return;
}
else if(t->element<key)
{
searchnode(t->right,key);
}
else if(t->element>key)
{
searchnode(t->left,key);
}
}
void avl::remove(int element)
{
removenode(root,element);
}
void avl::removenode(avlnode*&t,int element)
{if(t==NULL)
{
return;
}
if(t->element>element){
removenode(t->left,element);
t->height=max(height(t->left),height(t->right))+1;
if(height(t->right)-height(t->left)==2)
rotatewithrightchild(t);
}
else if(t->element<element)
{removenode(t->right,element);
t->height=max(height(t->left),height(t->right))+1;
if(height(t->right)-height(t->left)==2)
rotatewithleftchild(t);
}
else if(t->left!=NULL&&t->right!=NULL)
{int b=findmin(t->right);
if(b!=-1000){t->element=b;
removenode(t->right,t->element);}
}
else
{avlnode*p;
p=t;
t=(t->left!=NULL)?t->left:t->right;
delete p;
}
}
int main()
{
avl 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 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:
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