Answer to Question #205417 in Java | JSP | JSF for Rama

Question

1.

Write a java program to implement an A VL Tree with the following

operations:

A. Inset a node in the A VL Tree

B. Delete a node in the AVL Tree

C. Search a node in the AVL Tree

D. Print the nodes in the AVL Tree

E. Exit the program.

Implement the above operations in five different methods.

All the methods will be called from main method according to user choice.

Answer 1

import java.util.Scanner;  
class Node  
{      
    int el;  
    int h;    
    Node lc;  
    Node rc;  
    public Node()  
    {  
        lc = null;  
        rc = null;  
        el = 0;  
        h = 0;  
    }  
    public Node(int el)  
    {  
        lc = null;  
        rc = null;  
        this.el = el;  
        h = 0;  
    }       
}  


class ConstructAVLTree  
{  
    private Node rn;       
    public ConstructAVLTree()  
    {  
        rn = null;  
    }  
    public void removeAll()  
    {  
        rn = null;  
    }  
  
    public boolean isEmpty()  
    {  
        if(rn == null)  
            return true;  
        else   
            return false;  
    }  
    public void insertElement(int el)  
    {  
        rn= insertElement(el, rn);  
    }    
    private int getHeight(Node n )  
    {  
        return n == null ? -1 : n.h;  
    }  
      
    private int getMaxHeight(int leftNodeHeight, int rightNodeHeight)  
    {  
    return leftNodeHeight > rightNodeHeight ? leftNodeHeight : rightNodeHeight;  
    }    
    private Node insertElement(int el, Node n)  
    {  
        if (n == null)  
            n = new Node(el);  
        else if (el < n.el)  
        {  
            n.leftChild = insertElement( el, n.leftChild );  
            if( getHeight( node.leftChild ) - getHeight( node.rightChild ) == 2 )  
                if( element < node.leftChild.el )  
                    n = rotateWithLeftChild( n );  
                else  
                    n = doubleWithLeftChild( n);  
        }  
        else if( el > n.el )  
        {  
            n.rightChild = insertElement( el, n.rightChild );  
            if( getHeight( n.rightChild ) - getHeight( n.leftChild ) == 2 )  
                if( element > n.rightChild.element)  
                    n = rotateWithRightChild( n );  
                else  
                    n = doubleWithRightChild( n );  
        }  
        else  
            ;  // if the element is already present in the tree, we will do nothing   
        node.h = getMaxHeight( getHeight( node.leftChild ), getHeight( node.rightChild ) ) + 1;  
          
        return node;  
          
    }  
      
    // creating rotateWithLeftChild() method to perform rotation of binary tree node with left child        
    private Node rotateWithLeftChild(Node node2)  
    {  
        Node node1 = node2.leftChild;  
        node2.leftChild = node1.rightChild;  
        node1.rightChild = node2;  
        node2.h = getMaxHeight( getHeight( node2.leftChild ), getHeight( node2.rightChild ) ) + 1;  
        node1.h = getMaxHeight( getHeight( node1.leftChild ), node2.h ) + 1;  
        return node1;  
    }  
  
    // creating rotateWithRightChild() method to perform rotation of binary tree node with right child        
    private Node rotateWithRightChild(Node node1)  
    {  
        Node node2 = node1.rightChild;  
        node1.rightChild = node2.leftChild;  
        node2.leftChild = node1;  
        node1.h = getMaxHeight( getHeight( node1.leftChild ), getHeight( node1.rightChild ) ) + 1;  
        node2.h = getMaxHeight( getHeight( node2.rightChild ), node1.h ) + 1;  
        return node2;  
    }  
  
    //create doubleWithLeftChild() method to perform double rotation of binary tree node. This method first rotate the left child with its right child, and after that, node3 with the new left child  
    private Node doubleWithLeftChild(Node node3)  
    {  
        node3.leftChild = rotateWithRightChild( node3.leftChild );  
        return rotateWithLeftChild( node3 );  
    }  
  
    //create doubleWithRightChild() method to perform double rotation of binary tree node. This method first rotate the right child with its left child and after that node1 with the new right child  
    private Node doubleWithRightChild(Node node1)  
    {  
        node1.rightChild = rotateWithLeftChild( node1.rightChild );  
        return rotateWithRightChild( node1 );  
    }      
  
    //create getTotalNumberOfNodes() method to get total number of nodes in the AVL Tree  
    public int getTotalNumberOfNodes()  
    {  
        return getTotalNumberOfNodes(rootNode);  
    }  
    private int getTotalNumberOfNodes(Node head)  
    {  
        if (head == null)  
            return 0;  
        else  
        {  
            int length = 1;  
            length = length + getTotalNumberOfNodes(head.leftChild);  
            length = length + getTotalNumberOfNodes(head.rightChild);  
            return length;  
        }  
    }  
  
    //create searchElement() method to find an element in the AVL Tree  
    public boolean searchElement(int element)  
    {  
        return searchElement(rootNode, element);  
    }  
  
    private boolean searchElement(Node head, int element)  
    {  
        boolean check = false;  
        while ((head != null) && !check)  
        {  
            int headElement = head.element;  
            if (element < headElement)  
                head = head.leftChild;  
            else if (element > headElement)  
                head = head.rightChild;  
            else  
            {  
                check = true;  
                break;  
            }  
            check = searchElement(head, element);  
        }  
        return check;  
    }  
    // create inorderTraversal() method for traversing AVL Tree in in-order form  
    public void inorderTraversal()  
    {  
        inorderTraversal(rootNode);  
    }  
    private void inorderTraversal(Node head)  
    {  
        if (head != null)  
        {  
            inorderTraversal(head.leftChild);  
            System.out.print(head.element+" ");  
            inorderTraversal(head.rightChild);  
        }  
    }  
  
    // create preorderTraversal() method for traversing AVL Tree in pre-order form  
    public void preorderTraversal()  
    {  
        preorderTraversal(rootNode);  
    }  
    private void preorderTraversal(Node head)  
    {  
        if (head != null)  
        {  
            System.out.print(head.element+" ");  
            preorderTraversal(head.leftChild);               
            preorderTraversal(head.rightChild);  
        }  
    }  
      
    // create postorderTraversal() method for traversing AVL Tree in post-order form  
    public void postorderTraversal()  
    {  
        postorderTraversal(rootNode);  
    }  
      
    private void postorderTraversal(Node head)  
    {  
        if (head != null)  
        {  
            postorderTraversal(head.leftChild);               
            postorderTraversal(head.rightChild);  
            System.out.print(head.element+" ");  
        }  
    }       
}  
  
public class AVLTreeExample  
{  
    public static void main(String[] args)  
    {              
        Scanner sc = new Scanner(System.in);  
        ConstructAVLTree obj = new ConstructAVLTree();   
        
    }  
}