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\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.