#include<iostream.h>
//*******************class
treenode*********************************************
class
treenode
{
private:
int data;
treenode* right;
treenode* left;
int height;
public:
treenode();
int getdata();
friend class TREE;
};
//////////////////////treenode()/////////////////////////////////////////////
treenode::treenode()
{
right=NULL;
left=NULL;
height=-1;
}
////////////////////////getdata()/////////////////////////////////////////
int
treenode::getdata()
{
return data;
}
//******************class
TREE**********************************************
class
TREE
{
private:
treenode* root;
void tree_insert(treenode * &t,
treenode*a);
void right_rotation(treenode* &itm2);
void left_rotation(treenode *& itm2);
void double_left_rotation(treenode*&
bf);//double left rotation
void double_right_rotation(treenode*
&bf);//double right rotation
int height(treenode *t);
treenode* find_min(treenode *t);
int find_max(int v1, int v2);
public:
TREE();//constructor
treenode* getroot();//returns the value of
the root
void INSERT();
treenode*& DELTREE(treenode* t, int
x);
void in_order(treenode*t);
void post_order(treenode*t);
void pre_order(treenode*t);
};
//////////////////////TREE()////////////////////////////////////////
TREE::TREE()
{
root=NULL;
}
//////////////////////getroot()///////////////////////////////////////////
treenode* TREE::getroot()
{
return root;
}
////////////////////////tree_insert()////////////////////////////////////////
void
TREE::tree_insert(treenode * &t,treenode*TREE2)
{
if(t==NULL)
{
t=TREE2;
}
else
if(t->data<TREE2->data)
{
tree_insert(t->right,TREE2);
if(height(t->right)-height(t->left)==2)
{
if(TREE2->data>t->right->data)
left_rotation(t);
else
double_right_rotation(t);
}
}
else
if(t->data>TREE2->data)
{
tree_insert(t->left,TREE2);
if(height(t->left)-height(t->right)==2)
{
if(TREE2->data<t->left->data)
right_rotation(t);
else
double_left_rotation(t);
}
}
}
///////////////////right_rotation()/////////////////////////////////////////////
void
TREE::right_rotation(treenode* &itm2)
{
treenode *itm1 = itm2->left;
itm2->left=itm1->right;
itm1->right=itm2;
itm2=itm1;
}
//////////////////////left_rotation()//////////////////////////////////////////
void
TREE::left_rotation(treenode*&itm2)
{
treenode*itm1=itm2->right;
itm2->right=itm1->left;
itm1->left=itm2;
itm2=itm1;
}
/////////////////////double_left_rotation()///////////////////////////////////////
void
TREE::double_left_rotation(treenode * &bf)
{
treenode *itm2;
treenode *itm1;
itm2= bf->left;
itm1=itm2->right;
itm2->right=itm1->left;
itm1->left=itm2;
bf->left=itm1;
// treenode * k3=bf;
treenode * itm4=bf->left;
bf->left=itm4->right;
itm4->right=bf;
bf=itm4;
}
////////////////////double_right_rotation()////////////////////////////////////////
void
TREE::double_right_rotation(treenode * &bf)
{
treenode*itm2;
treenode*itm1;
itm2=bf->right;
itm1=itm2->left;
itm2->left=itm1->right;
itm1->right=itm2;
bf->right=itm1;
// treenode *k3=bf;
treenode *itm4=bf->right;
bf->right=itm4->left;
itm4->left=bf;
bf=itm4;
}
///////////////////////////in_order()/////////////////////////////////////////
void
TREE::in_order(treenode *t)
{
if(t==NULL)
{
return;
}
in_order(t->left);
cout<<t->data<<endl;
in_order(t->right);
}
/////////////////////////post_order/////////////////////////////////////////
void
TREE::post_order(treenode *t)
{
if(t==NULL)
{
return;
}
post_order(t->left);
post_order(t->right);
cout<<t->data<<endl;
}
///////////////////////pre_order()////////////////////////////////////////////
void
TREE::pre_order(treenode *t)
{
if(t==NULL)
{
return;
}
cout<<t->data<<endl;
pre_order(t->left);
pre_order(t->right);
}
/////////////////////DELTREE()/////////////////////////////////////////////
treenode*&
TREE::DELTREE(treenode *t,int x)
{
treenode* temp_cell;
treenode* child;
if(t==NULL)
{
cout<<"item not in the
tree"<<endl;
}
else
if(t->data>x)
{
t->left=DELTREE(t->left,x);
if(height(t->right)-height(t->left)==2)
{
if(x>t->right->data)
left_rotation(t);
else
double_right_rotation(t);
}
}
else
if(t->data<x)
t->right=DELTREE(t->right,x);
if(height(t->left)-height(t->right)==2)
{
if(x<t->left->data)
right_rotation(t);
else
double_left_rotation(t);
}
else
if(t->left &&
t->right)
{
temp_cell=find_min(t->right);
t->data=temp_cell->data;
t->right=DELTREE(t->right,t->data);
}
else
{
temp_cell=t;
if(t->left==NULL)
child=t->right;
if(t->right==NULL)
child=t->left;
delete temp_cell;
return child;
}
return t;
}
////////////////////////height()//////////////////////////////////////
int
TREE::height(treenode* t)
{
if(t==NULL)
{
return -1;
}
else
return
1+find_max(height(t->left),height(t->right));
}
////////////////////////find_max()//////////////////////////////////////////
int
TREE::find_max(int v1, int v2)
{
if(v1>v2)
return v1;
else
return v2;
}
/////////////////////////////find_min()///////////////////////////////
treenode
* TREE::find_min(treenode* t)
{
if(t==NULL)
return NULL;
else
if(t->left==NULL)
return t;
else
return(find_min(t->left));
}
/////////////////////INSERT()//////////////////////////////////////
void
TREE::INSERT()
{
treenode* p=new treenode;
cout<<"enter the number you
want to insert"<<endl;
cin>>p->data;
p->left=NULL;
p->right=NULL;
tree_insert(root,p);//calls to the private
insert function
}