Help with implementing isCompleteTree JAVA. I have to check if the given array i

ID: 3714893 • Letter: H

Question

Help with implementing isCompleteTree JAVA. I have to check if the given array is a complete binary tree.

CODE:

import java.util.List;
import java.util.ArrayList;

public class ArrayHeapChecker {

/*
* This nested class contains a completed implementation of Entry.
*
* You do not need to edit this class.
*/
public static class Entry<K extends Comparable<K>, V> {

private K key;
private V value;

public Entry(K key, V value) {
this.key = key;
this.value = value;
}

public K getKey() {return key;}
public V getValue() {return value;}
public void setKey(K key) {this.key = key;}
public void setValue(V value) {this.value = value;}
}

/**

* Checks if the given array is a complete binary tree.

* @param entries

* array of entries to be tested

* @return true if the input array encodes a complete binary tree, false otherwise

public static <K extends Comparable<K>, V> boolean isCompleteBinaryTree(List<Entry<K, V>> entries) {

if(!isBinaryTree(entries)) {

return false;

}

// TODO: implement this

return true;

}

Explanation / Answer

Program:

//Java Program to impliment BST

import java.util.Scanner;

// Create class BSTNode
class BSTNode
{
     BSTNode left, right;
     int data;

     //Create Constructor
     public BSTNode()
     {
         left = null;   //both nodes are null pointers
         right = null;
         data = 0;
     }
     //Create Constructor
     public BSTNode(int n)
     {
         left = null;
         right = null;
         data = n;
     }
     //Create Function to set left node
     public void setLeft(BSTNode n)
     {
         left = n;
     }
     //Create Function to set right node

     public void setRight(BSTNode n)
     {
         right = n;
     }
     //get left node
     public BSTNode getLeft()
     {
         return left;
     }
     // Function to get right node
     public BSTNode getRight()
     {
         return right;
     }
     //get left node
     public void setData(int d)
     {
         data = d;
     }
     // Function to get data from node
     public int getData()
     {
         return data;
     }
}

// Class Binary Search Tree
class BST
{
     private BSTNode root;

     // Constructor
     public BST()
     {
         root = null;
     }
     //Function to check if tree is empty
     public boolean isEmpty()
     {
         return root == null;
     }
     // Functions to insert data
     public void insert(int data)
     {
         root = insert(root, data);
     }
     // insert data recursively
     private BSTNode insert(BSTNode node, int data)
     {
         if (node == null) //check is it empty or not
             node = new BSTNode(data);
         else
         {
             if (data <= node.getData())
                 node.left = insert(node.left, data);
             else
                 node.right = insert(node.right, data);
         }
         return node;
     }
     // Functions to delete data
     public void delete(int k)
     {
         if (isEmpty())
             System.out.println("Tree Empty");
         else if (search(k) == false)
             System.out.println("Sorry "+ k +" is not present");
         else
         {
             root = delete(root, k);
             System.out.println(k+ " deleted from the tree");
         }
     }
     private BSTNode delete(BSTNode root, int k) //delete element from BST
     {
         BSTNode p, p2, n;     //p1 and p2 left and right pointers
         if (root.getData() == k)   //get data from the list
         {
             BSTNode lt, rt;
             lt = root.getLeft();
             rt = root.getRight();
             if (lt == null && rt == null)
                 return null;
             else if (lt == null)
             {
                 p = rt;
                 return p;
             }
             else if (rt == null)
             {
                 p = lt;
                 return p;
             }
             else
             {//find element is there or not there
                 p2 = rt;
                 p = rt;
                 while (p.getLeft() != null)
                     p = p.getLeft();
                 p.setLeft(lt);
                 return p2;
             }
         }
         if (k < root.getData())
         {
             n = delete(root.getLeft(), k);
             root.setLeft(n);
         }
         else
         {
             n = delete(root.getRight(), k);
             root.setRight(n);
         }
         return root;
     }
     // Functions to count number of nodes
     public int countNodes()
     {
         return countNodes(root);
     }
     // Function to count number of nodes recursively
     private int countNodes(BSTNode r)
     {
         if (r == null)
             return 0;
         else
         {
             int l = 1;
             l += countNodes(r.getLeft());
             l += countNodes(r.getRight());
             return l;
         }
     }
     // Functions to search for an element
     public boolean search(int val)
     {
         return search(root, val);
     }
     // Function to search for an element recursively
     private boolean search(BSTNode r, int val)
     {
         boolean found = false;
         while ((r != null) && !found)
         {
             int rval = r.getData();
             if (val < rval)
                 r = r.getLeft();
             else if (val > rval)
                 r = r.getRight();
             else
             {
                 found = true;
                 break;
             }
             found = search(r, val);
         }
         return found;
     }
     // Function for inorder traversal
     public void inorder()
     {
         inorder(root);
     }
     private void inorder(BSTNode r)
     {
         if (r != null)
         {
             inorder(r.getLeft());
             System.out.print(r.getData() +" ");
             inorder(r.getRight());
         }
     }
     // Function for preorder traversal
     public void preorder()
     {
         preorder(root);
     }
     private void preorder(BSTNode r)
     {
         if (r != null)
         {
             System.out.print(r.getData() +" ");
             preorder(r.getLeft());
             preorder(r.getRight());
         }
     }
     // Function for postorder traversal
     public void postorder()
     {
         postorder(root);
     }
     private void postorder(BSTNode r)
     {
         if (r != null)
         {
             postorder(r.getLeft());
             postorder(r.getRight());
             System.out.print(r.getData() +" ");
         }
     }
}

// Class BinarySearchTree
public class BinarySearchTree
{
     public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        // Creating object of BST
        BST bst = new BST();
        System.out.println("Binary Search Tree Test ");
        char ch;
  int choice;
        // Perform tree operations
        do
        {
            System.out.println(" Binary Search Tree Operations ");
            System.out.println("1. Insert ");
            System.out.println("2. Delete");
            System.out.println("3. Search");
            System.out.println("4. Count nodes");
            System.out.println("5. Check empty");
   System.out.println("6. Display");
   System.out.println("7. Eit");
            System.out.println(" Please selec your choice ");

             choice = scan.nextInt();
            switch (choice)
            {
            case 1 :
                System.out.println("Enter integer element to insert");
                bst.insert( scan.nextInt() );
                break;
            case 2 :
                System.out.println("Enter integer element to delete");
                bst.delete( scan.nextInt() );
                break;
            case 3 :
                System.out.println("Enter integer element to search");
                System.out.println("Search result : "+ bst.search( scan.nextInt() ));
                break;
            case 4 :
                System.out.println("Nodes = "+ bst.countNodes());
                break;
            case 5 :
                System.out.println("Empty status = "+ bst.isEmpty());
                break;
            case 6:
    System.out.print(" Post order : ");
    bst.postorder();
    System.out.print(" Pre order : ");
    bst.preorder();
    System.out.print(" In order : ");
    bst.inorder();
            break;

            }

        } while (choice!=7);
    }
}

Output:

Binary Search Tree Operations