In this lab exercise, you will be completing a partial implementation of a BinarySearchTree class for integer numbers. Download the BinarySearchTree.java file and Lab6Driver.java files from C4, and add them to a new Java project.

The driver contains several test cases for insertion and removal. BSTTest0() generates random numbers and inserts them into a BinarySearchTree object. The test cases BSTTest1(),…, BSTTest8() test specific situations of removing keys from a BST. You can run each test case separately.

Methods to complete

CalculateHeight – this method recursively calculates the height of the (sub)tree rooted at its parameter. Hints:

• How is the height of a node related to the height of its subtrees?

• Math.max(a,b) returns the maximum of a and b.

Insert – inserts an item into the BinarySearchTree object. This can be completed iteratively in the public method Insert(int item), or handed off to a recursive private method Insert(BSTNode nd, int item). Duplicate keys will be allowed and should go into the left subtree with the rule ???????????????? ≤????????????????????????????<????????????ℎ????.

Remove – Removes the specified key from the BinarySearchTree object, using the proper (non-lazy) method described in the lecture slides. The method returns false if the key is not found. Complete the code for the recursive method Remove(BSTNode nd, int item) that is called by the Remove method. Use the predecesssor replacement rule for the 2-child case. (for duplicate keys in the tree: only remove one key)

For all methods, pay special attention to special cases – empty tree, tree contains one element, etc.// File:        BinarySearchTree.java
// Author:      Geoffrey Tien/ Rita Ester
// Date:        March 20, 2017
// Description: BinarySearchTree class
//              

class BSTNode {
  //public member attributes
  // direct access for simplicity
  public int data;
  public BSTNode left, right;
 
  // Default/leaf node constructor
  public BSTNode(int value)
  {
    data = value;
    left = null;
    right = null;
  }
}

public class BinarySearchTree {
  protected BSTNode root;
  private int size;
 
  // default constructor
  public BinarySearchTree()
  {
    root = null;
    size = 0;
  }
 
  // returns the number of items stored in the tree
  public int Size()
  {
    return size;
  }
 
  // returns the height of the tree
  // an empty tree has height -1
  // a tree of only the root has height 0
  public int Height()
  {
    return CalculateHeight(root);
  }
 
  // Recursively computes the height of a subtree rooted at nd
  // Use Math.max to choose the taller of nd's two children
  // the height of an empty tree is -1.
  private int CalculateHeight(BSTNode nd)
  {
    // to be completed
    
  }
 
  // Search function
  // Returns true if the search term is in the tree, false otherwise
  // May be implemented iteratively in this function, or recursively
  //   using your own private helper function
  public boolean Contains(int item)
  {
    return Contains(root, item);
  }
 
  // recursive Contains method
  private boolean Contains(BSTNode nd, int item)
  {
    if (nd == null)
      return false;
    else if (nd.data == item)
      return true;
    else if (item < nd.data)
      return Contains(nd.left, item);
    else // nd.data < item
      return Contains(nd.right, item);
  }
 
  // Insert function
  // Inserts a new leaf node while maintaining BST properties
  // May be completed iteratively in this method,
  // or recursively using a private method.
  // Allow duplicates with the rule: left < current <= right
  public void Insert(int item)
  {
    // to be completed
    
  }
 
  // recursive insert method
  private void Insert(BSTNode nd, int item)
  {
    // to be completed, if recursive solution is chosen
    
  }
 
  // returns the value of the smallest key in the tree
  // Throws IllegalStateException if tree is empty
  public int FindMin() throws IllegalStateException
  {
    if (size <= 0)
      throw new IllegalStateException("FindMin: tree is empty");
    else
    {
      BSTNode current = root;
      while (current.left != null)
      {
        current = current.left;
      }
      return current.data;
    }
  }
 
  // returns the value of the largest key in the tree
  // Throws IllegalStateException if tree is empty
  public int FindMax() throws IllegalStateException
  {
    if (size <= 0)
      throw new IllegalStateException("FindMax: tree is empty");
    else
    {
      BSTNode current = root;
      while (current.right != null)
      {
        current = current.right;
      }
      return current.data;
    }
  }
 
  // returns false if item is not in the tree
  // removes and returns true if item can be found and removed
  // be aware of special cases
  // - removing root
  // - removing the only node in the tree
  // Use the Predecessor rule for the 2-child case
  public boolean Remove(int item)
  {
    // Can be more efficient, since this will search the
    // tree twice if the item exists
    if (!Contains(item))
      return false;
    else
    {
      root = Remove(root, item);
      size -= 1;
      return true;
    }
  }
 
  // Recursive Remove, returns the root of the subtree after removal
  private BSTNode Remove(BSTNode nd, int item)
  {
    // to be completed
  }
 
 
  // In-order traversal, prints tree contents on a single line
  // NOTE: implicit base case if nd == null, do not recurse or visit.
  public void InOrderPrint(BSTNode nd)
  {
    if (nd != null)
    {
      InOrderPrint(nd.left);
      System.out.print(nd.data + "\t");
      InOrderPrint(nd.right);
    }
  }
 
  // returns a reference to the root node of the tree
  // note that this can be dangerous in practice!
  public BSTNode GetRoot()
  {
    return root;
  }
 
  // Initial call to print the contents/structure of the tree.
  public String PrintTree()
  {
    return PrintTree(root, 0, new StringBuilder()).toString();
  }
 
  // recursively prints the contents/structure of the tree,
  // rotated counter-clockwise 90 degrees.
  // Use a reversed in-order traversal.
  // parameter: the number of tab characters to insert
  // example output: for a tree with root 12, left child 5, right child 17
  //                 print the following tree structure:
  //     17
  // 12
  //     5
  private StringBuilder PrintTree(BSTNode nd, int level, StringBuilder tree)
  {
    if (nd == null)
    {
      return tree;
    }
    else
    {
      PrintTree(nd.right, level+1, tree);
      for (int i = 0; i < level; i++)
        tree.append("\t");
      tree.append(nd.data + "\n");
      PrintTree(nd.left, level+1, tree);
      return tree;
    }
  }
}
// File:        Lab6Driver.java
// Author:      Geoffrey Tien/Rita Ester
// Date:        June 9, 2017
// Description: Driver file for CSCI 225 Lab 6

import java.util.Random;

public class Lab6Driver2 {
  static Random rnd = new Random();
  static final int maxvalue = 100; // the largest integer that can be randomly generated.
  static final int numitems = 9; // number of items to insert, can be changed
  static final int numitemstoremove = 3;
  static int[] contents = new int[numitems];
 
  public static void main(String[] args)
  {
    rnd.setSeed(System.currentTimeMillis());
    BSTTest0();
     
      //BSTTest1();
      //BSTTest2();
      //BSTTest3();
      //BSTTest4();
      //BSTTest5();
      //BSTTest6();
      //BSTTest7();
      //BSTTest8();
  }
 
  private static void PrintStats(BinarySearchTree tree){
     System.out.println("Printing tree...");
     System.out.println(tree.PrintTree());
     System.out.print("Tree height: " + tree.Height());
     System.out.print("\tIn-order contents: ");
     tree.InOrderPrint(tree.GetRoot());
  }
 
 
  public static void BSTTest0()
  {
    BinarySearchTree treeA = new BinarySearchTree();
    System.out.println("New BinarySearchTree created.");
   
    // insert random-valued nodes into tree
    int item;
    for (int i = 0; i < numitems; i++)
    {
      item = rnd.nextInt(maxvalue);
      treeA.Insert(item);
      contents[i] = item;
    }
    System.out.println(numitems + " random items inserted. ");
    PrintStats (treeA);
       
    System.out.println("\nRemoving items...");
    for (int i = 0; i < numitemstoremove; i++)
    {
      int index = rnd.nextInt(numitems-1);
      item = contents[index];
      System.out.println("Removing " + item + "...");
      treeA.Remove(item);
    }
    PrintStats (treeA);
  }
 
  public static void BSTTest1()
  // removing the key from a single node tree.
  {
    BinarySearchTree treeA = new BinarySearchTree();
    System.out.println("\nTest 1: removing the key from a single node tree");
   
    // insert nodes into tree
    int[] keys ={13};
    for (int i = 0; i < keys.length; i++)
    {
      treeA.Insert(keys[i]);
    }
    System.out.print(keys.length + " keys inserted. ");
    PrintStats (treeA);
   
    System.out.println("\nRemoving key 13...");
    treeA.Remove(13);
   
    PrintStats (treeA);
  }
 
  public static void BSTTest2()
  // removing a leaf from a tree.
  {
    BinarySearchTree treeA = new BinarySearchTree();
    System.out.println("\nTest 2: removing a leaf from a tree.");
   
    // insert nodes into tree
    int[] keys ={13, 3, 23};
    for (int i = 0; i < keys.length; i++)
    {
      treeA.Insert(keys[i]);
    }
    PrintStats (treeA);
   
    System.out.println("\nRemoving key 3...");
    treeA.Remove(3);
   
    PrintStats (treeA);
  }
 
  public static void BSTTest3()
  // removing the root key from a tree and finding a successor.
  {
    BinarySearchTree treeA = new BinarySearchTree();
    System.out.println("\nTest 3: removing the root key from a tree and finding a successor");
   
    // insert nodes into tree
    int[] keys ={13, 3, 23, 8};
    for (int i = 0; i < keys.length; i++)
    {
      treeA.Insert(keys[i]);
    }
    PrintStats (treeA);
   
    System.out.println("\nRemoving key 13...");
    treeA.Remove(13);
   
    PrintStats (treeA);
  }
 
  public static void BSTTest4()
  // removing an inner node with no right tree.
  {
    BinarySearchTree treeA = new BinarySearchTree();
    System.out.println("\nTest 4: removing an inner node with no right subtree");  
    // insert nodes into tree
    int[] keys ={13, 6, 23, 4};
    for (int i = 0; i < keys.length; i++)
    {
      treeA.Insert(keys[i]);
    }
    PrintStats (treeA);  
    System.out.println("\nRemoving key 6...");
    treeA.Remove(6);  
    PrintStats (treeA);
  }
 
  public static void BSTTest5()
  // removing an inner node with no left subtree.
  {
    BinarySearchTree treeA = new BinarySearchTree();
    System.out.println("\nTest 5: removing an inner node with no left subtree");  
    // insert nodes into tree
    int[] keys ={13, 6, 23, 8};
    for (int i = 0; i < keys.length; i++)
    {
      treeA.Insert(keys[i]);
    }
    PrintStats (treeA);  
    System.out.println("\nRemoving key 6...");
    treeA.Remove(6);  
    PrintStats (treeA);
  }
 
  public static void BSTTest6()
  // removing an inner node with a left tree and a right subtree.
  {
    BinarySearchTree treeA = new BinarySearchTree();
    System.out.println("\nTest 6: removing an inner node with left and right subtrees");  
    // insert nodes into tree
    int[] keys ={33,13,43, 6, 23, 3};
    for (int i = 0; i < keys.length; i++)
    {
      treeA.Insert(keys[i]);
    }
    PrintStats (treeA);  
    System.out.println("\nRemoving key 13...");
    treeA.Remove(13);  
    PrintStats (treeA);
  }
 
  public static void BSTTest7()
  // removing an inner node with a left tree and a right subtree.
  {
    BinarySearchTree treeA = new BinarySearchTree();
    System.out.println("\nTest 7: removing an inner node with left and right subtrees");  
    // insert nodes into tree
    int[] keys ={33,13,43, 6, 23, 3,8};
    for (int i = 0; i < keys.length; i++)
    {
      treeA.Insert(keys[i]);
    }
    PrintStats (treeA);  
    System.out.println("\nRemoving key 13...");
    treeA.Remove(13);  
    PrintStats (treeA);
  }
 
  public static void BSTTest8()
  // removing an inner node with a left tree and a right subtree.
  {
    BinarySearchTree treeA = new BinarySearchTree();
    System.out.println("\nTest 7: removing an inner node with left and right subtrees");  
    // insert nodes into tree
    int[] keys ={33,13,43, 6, 23, 3,8,7};
    for (int i = 0; i < keys.length; i++)
    {
      treeA.Insert(keys[i]);
    }
    PrintStats (treeA);  
    System.out.println("\nRemoving key 13...");
    treeA.Remove(13);  
    PrintStats (treeA);
  }
 
 
}

Attachments:

• 1511266365-lab6-1171.pdf