3
\$\begingroup\$

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();
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.