Please suggest some ways to improve it. It takes input values from the user and builds a height balanced tree (AVL tree) after applying Rotation and then prints the in order traversal of the tree along with the Balance factor of each node.
#include<iostream.h> //Necesary header files
#include<conio.h>
struct Node //Basic structure of an node.
{
int data; //data of each mode.
int bf; //Balance Factor(for an AVL tree it should be equal 1, 0, -1 )
int hol; //height of left subtree rooted at node.
int hor; //height of right subtree rooted at node.
char child; //'r'->right child of its parent, 'l'->left child of its parent
Node *left; //Address of left Node rooted at current node.
Node *right; //Address of right Node rooted at current node.
};
Node *root; //root of the AVL tree.
class Tree
{
private:
Node *p, *A, *B, *C, *swp; //*p=temprary pointer used for insertion of a new node, A=first imbalanced node, B=child of node A, C=new inserted node.
int count, hor, hol, tmp2; //temprary variables used for swapping purpose.
public:
Tree() //A default constructor to initialise values to zero.
{
A=B=C=root=NULL;
count=0;
hol=hor=0;
}
void Insertion();
void Traverse(Node *);
protected:
void Rotation(Node *);
void BfCal(Node *, char ch);
void SearchPos(Node *, Node *);
void Initialise(Node *);
};
void Tree::Insertion() //creates a new node.
{
p=new Node;
p->left=NULL;
p->right=NULL;
p->bf=p->hol=p->hor=0;
if(root==NULL) //if it is a first node then t should be root.
{
cout<<"Root Value to be Inserted:";
cin>>p->data;
root=p;
p->child=NULL;
}
else
{
cout<<"\n\nEnter Value To be Inserted:";
cin>>p->data;
SearchPos(root, p); //find a proper position for the new noe and inserts the node there.
BfCal(root, NULL); //calculates the balance factor.
Rotation(root); //checks balance factor and applies rotation.
}
}
void Tree::SearchPos(Node *rt,Node *p) //Finds a proper position for the new node to be inserted as per the property of a Binary Search Tree.
{
if(rt->left==NULL && rt->data>p->data) //checks the basic property of a Binary Search Tree.
{
rt->left=p;
p->child='l';
C=p; //C=inserted node.
return;
}
else if(rt->right==NULL && p->data>rt->data)
{
rt->right=p;
p->child='r';
C=p;
return;
}
if(rt->left!=NULL && rt->data>p->data)
{
SearchPos(rt->left, p);
}
else if(rt->right!=NULL && rt->data<p->data)
{
SearchPos(rt->right, p);
}
}
void Tree::Traverse(Node *tmp) //Inorder traversel of tree.
{
if(tmp->left==NULL && tmp->right==NULL)
{
cout<<tmp->data<<"\thas\t"<<"BF:"<<tmp->bf<<"\tchild:"<<tmp->child<<endl;
return;
}
if(tmp->left!=NULL||(tmp->left!=NULL && tmp->right==NULL))
{
Traverse(tmp->left);
}
cout<<tmp->data<<"\thas\t"<<"BF:"<<tmp->bf<<"\tchild:"<<tmp->child<<endl;
if(tmp->right!=NULL||(tmp->right!=NULL && tmp->left==NULL))
{
Traverse(tmp->right);
}
}
void Tree::BfCal(Node *tmp, char ch) //Calculates Balance Factor for each node.
{
if(tmp->left==NULL && tmp->right==NULL) //hor, hol of a node should be zero for a leap.
{
if(ch=='l')
hol=0;
else
hor=0;
tmp->bf=0;
return;
}
if(tmp->left!=NULL||(tmp->left!=NULL && tmp->right==NULL))
{
BfCal(tmp->left,'l');
tmp->hol=++hol;
}
if(tmp->right!=NULL||(tmp->right!=NULL && tmp->left==NULL))
{
BfCal(tmp->right,'r');
tmp->hor=++hor;
}
if(tmp->left!=NULL && tmp->right!=NULL)
tmp->bf=hol-hor;
else if(tmp->left!=NULL && tmp->right==NULL)
{
tmp->bf=hol;
}
else if(tmp->left==NULL && tmp->right!=NULL)
tmp->bf=-hor;
}
void Tree::Rotation(Node *tmp) //Apply rotation if Balance Factor not equals to 0, 1, -1.
{
if(tmp->bf!=0 && tmp->bf!=-1 && tmp->bf!=1)
{
A=tmp; //A=first node that have been imbalanced from the top.
char child=A->child;
if(A->data>C->data)
{
B=tmp->left; //child of a node.
cout<<endl<<"A->data:"<<A->data<<endl;
cout<<"B->data:"<<B->data<<endl;
cout<<"C->data:"<<C->data<<endl;
if(B->child=='l' && C->child=='l')
{
tmp2=A->data; //l-l rotation's starts.
A->data=B->data; // Positions of A and B are Swapped.
B->data=tmp2;
swp=A->left;
A->left=A->left->left;
swp->left=swp->right;
swp->right=A->right;
A->right=swp;
A->right->child='r';
A->right->left->child='l'; //ends.
}
else if(B->child=='l' && C->child=='r')
{
tmp2=A->data; //r-l rotation's code starts.
A->data=A->left->right->data; //C is made the parent of A, B.
A->left->right->data=tmp2;
swp=A->left->right;
A->left->right=A->left->right->left;
swp->left=swp->right;
swp->right=A->right;
A->right=swp;
A->left->right->child='l';
A->right->left->child='r';
}
}
else if(A->data<C->data)
{
B=tmp->right;
cout<<endl<<"A->data:"<<A->data<<endl;
cout<<"B->data:"<<B->data<<endl;
cout<<"C->data:"<<C->data<<endl;
if(A->child=='r' && B->child=='r')
{
tmp2=A->data; //r-r rotation's code starts.
A->data=B->data; //Positions of A, B are Swapped.
B->data=tmp2;
swp=A->right;
A->right=A->right->right;
swp->right=swp->left;
swp->left=A->left;
A->left=swp;
A->left->child='l';
A->left->right->child='r'; //ends.
}
else if(B->child=='r' && C->child=='l')
{
tmp2=A->data; //r-l rotation's code starts.
A->data=A->right->left->data; // C is made the parent of A, B.
A->right->left->data=tmp2;
swp=A->right->left;
A->right->left=A->right->left->right;
swp->right=swp->left;
swp->left=A->left;
A->left=swp;
A->right->left->child='l';
A->left->right->child='r';
}
}
cout<<endl<<"Rotation Performed."<<endl;
Initialise(A);
BfCal(A, child); //again calculates Banace Factor of each node after applying rotation.
}
else
{
if(tmp->left==NULL && tmp->right==NULL)
{
return;
}
if(tmp->left!=NULL||(tmp->left!=NULL && tmp->right==NULL))
{
Rotation(tmp->left);
}
if(tmp->right!=NULL||(tmp->right!=NULL && tmp->left==NULL))
{
Rotation(tmp->right);
}
}
}
void Tree::Initialise(Node *tmp) //Initialise all bf, hor, hol of a node to 0.
{
if(tmp->left==NULL && tmp->right==NULL)
{
p->bf=p->hol=p->hor=0;
return;
}
if(tmp->left!=NULL||(tmp->left!=NULL && tmp->right==NULL))
{
Traverse(tmp->left);
}
p->bf=p->hol=p->hor=0;
if(tmp->right!=NULL||(tmp->right!=NULL && tmp->left==NULL))
{
Traverse(tmp->right);
}
}
void main()
{
clrscr();
Tree t;
char choice;
do
{
t.Insertion(); //Inserts new nodes if choice=='y' OR choice=='Y'
cout<<"Values Fetched:-"<<endl;
t.Traverse(root); //Inorder traversal of the tree.
cout<<"\n\nMore to insert(y/n):";
cin>>choice;
}while(choice=='y'||choice=='Y');
getch();
}