Part 1: BST Class (50 pts)

• Your job for this lab is to write a BST class given the starter code provided below.
• Note that, for the purposes of this assignment, the starter code has been slightly modified from the code and algorithms given in the lessons.
• Create a new project folder in Eclipse and copy and paste the following into a file named BST.java

/** * BST.java * @author * @author * CIS 22C Lab 5 */ import java.util.NoSuchElementException; import java.util.Comparator; public class BST { private class Node { private T data; private Node left; private Node right; public Node(T data) { this.data = data; left = null; right = null; } } private Node root; /***CONSTRUCTORS***/ /** * Default constructor for BST * sets root to null */ public BST() { //fill in here } /** * Copy constructor for BST * @param bst the BST of which * to make a copy. * @param c the way the tree * is organized */ public BST(BST bst, Comparator c) { //fill in here } /** * Helper method for copy constructor * @param node the node containing * data to copy * @param c the way the tree is organized */ private void copyHelper(Node node, Comparator c) { //fill in here } /***ACCESSORS***/ /** * Returns the data stored in the root * @precondition !isEmpty() * @return the data stored in the root * @throws NoSuchElementException when * precondition is violated */ public T getRoot() throws NoSuchElementException{ return null; } /** * Determines whether the tree is empty * @return whether the tree is empty */ public boolean isEmpty() { return false; } /** * Returns the current size of the * tree (number of nodes) * @return the size of the tree */ public int getSize() { return -1; } /** * Helper method for the getSize method * @param node the current node to count * @return the size of the tree */ private int getSize(Node node) { return -1; } /** * Returns the height of tree by * counting edges. * @return the height of the tree */ public int getHeight() { return -1; } /** * Helper method for getHeight method * @param node the current * node whose height to count * @return the height of the tree */ private int getHeight(Node node) { return -1; } /** * Returns the smallest value in the tree * @precondition !isEmpty() * @return the smallest value in the tree * @throws NoSuchElementException when the * precondition is violated */ public T findMin() throws NoSuchElementException{ return null; } /** * Recursive helper method to findMin method * @param node the current node to check * if it is the smallest * @return the smallest value in the tree */ private T findMin(Node node) { return null; } /** * Returns the largest value in the tree * @precondition !isEmpty() * @return the largest value in the tree * @throws NoSuchElementException when the * precondition is violated */ public T findMax() throws NoSuchElementException{ return null; } /** * Recursive helper method to findMax method * @param node the current node to check * if it is the largest * @return the largest value in the tree */ private T findMax(Node node) { return null; } /** * Searches for a specified value * in the tree * @param data the value to search for * @param c the Comparator that indicates the way * the data in the tree was ordered * @return the data stored in that Node * of the tree is found or null otherwise */ public T search(T data, Comparator c) { return null; } /** * Helper method for the search method * @param data the data to search for * @param node the current node to check * @param c the Comparator that determines * how the BST is organized * @return the data stored in that Node * of the tree is found or null otherwise */ private T search(T data, Node node, Comparator c) { return null; } /***MUTATORS***/ /** * Inserts a new node in the tree * @param data the data to insert * @param c the Comparator indicating * how data in the tree is ordered */ public void insert(T data, Comparator c) { //fill in here } /** * Helper method to insert * Inserts a new value in the tree * @param data the data to insert * @param node the current node in the * search for the correct location to insert * @param c the Comparator indicating * how data in the tree is ordered */ private void insert(T data, Node node, Comparator c) { //fill in here } /** * Removes a value from the BST * @param data the value to remove * @param c the Comparator indicating * how data in the tree is organized * Note: updates nothing when the element * is not in the tree */ public void remove(T data, Comparator c) { //fill in here } /** * Helper method to the remove method * @param data the data to remove * @param node the current node * @param c the Comparator indicating how * data in the tree is organized * @return an updated reference variable */ private Node remove(T data, Node node, Comparator c) { return null; } /***ADDITONAL OPERATIONS***/ /** * Prints the data in pre order * to the console followed by a new * line */ public void preOrderPrint() { //fill in here System.out.println(); } /** * Helper method to preOrderPrint method * Prints the data in pre order * to the console followed by a new line */ private void preOrderPrint(Node node) { //fill in here } /** * Prints the data in sorted order * to the console followed by a new line */ public void inOrderPrint() { //fill in here System.out.println(); } /** * Helper method to inOrderPrint method * Prints the data in sorted order * to the console followed by a new line */ private void inOrderPrint(Node node) { //fill in here } /** * Prints the data in post order * to the console followed by a new line */ public void postOrderPrint() { System.out.println(); } /** * Helper method to postOrderPrint method * Prints the data in post order * to the console */ private void postOrderPrint(Node node) { //fill in here } }

• Starter code for for the insert method is given in Lesson 10
  • You must use this starter code when you write your method
  • However, you must also update to include the Comparator
• Starter code for pre, post and inOrderPrint given in Lesson 11
  • You must use this starter code when you write your method
• Starter code for search, findMin, and remove given in Lesson 12
  • You must use this starter code when you write your method
  • However, you must also update to include the Comparator
• Hint for writing copy constructor, getSize: Adapt an appropriate tree traversal (preOrderPrint, inOrderPrint, postOrderPrint).
  • Your code does not look like a light adaptation of one of the tree traversal algorithms provided in the class notes, then I will not give you credit for these methods.
  • You can figure it out for yourself - rather than copying code you find online!
• Hint for getHeight: Make sure you recognize that the height of a null if -1 (as covered in class) or you will not get the correct output from this method.
• For all of these recursive methods, you will understand the methods better if you draw the method call stack and trace through an example of pushing and popping method calls (stack frames) from the stack memory.
• Final Hint: Draw the trees that you use in your testing. If you understand what the tree looks like then you will know what output the methods are supposed to give.
• A Word on the Comparator:
• For testing purposes, you may wish to remove the Comparator parameters from the methods, and add them back in for part 2 of this assignment.
• If you took CIS 36B from me, you studied the Comparable interface and the compareTo method is some detail. The compareTo method provides only one way of organizing two Objects relative to each other
• But, what if you want to organize Objects relative to each other in several different ways? Enter the Comparator interface with its compare method.
• You are required to research Comparator and compare for this assignment. I suggest you begin with the following resources:
• Oracle Documentation on Comparator (Links to an external site.)
• Java Comparator Tutorial (Links to an external site.)