Lab 6 (100 pts) return -1;Due Monday, February 18 at 11:59pm on Canvas Pair Programming Required or No Credit!
Lab 6 Specifications:
* BST.java * @author * @author * CIS 22C Lab 6 */ import java.util.NoSuchElementException; public class BST<T extends Comparable<T>> { 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() { } /** * Copy constructor for BST * @param bst the BST to make * a copy of */ public BST(BST<T> bst) { } /** * Helper method for copy constructor * @param node the node containing * data to copy */ private void copyHelper(Node node) { } /***ACCESSORS***/ /** * Returns the data stored in the root * @precondition !isEmpty() * @return the data stored in the root * @throws NoSuchElementException when * preconditon 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() { } /** * 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 Integer.MIN_VALUE; //remove this. just a default value } /** * 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 Integer.MIN_VALUE; //remove this. just a default value } /** * 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; } /** * 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; } /** * 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 * @return whether the value is stored * in the tree */ public boolean search(T data) { return false; } /** * Helper method for the search method * @param data the data to search for * @param node the current node to check * @return whether the data is stored * in the tree */ private boolean search(T data, Node node) { return false; } /** * Determines whether two trees store * identical data in the same structural * position in the tree * @param o another Object * @return whether the two trees are equal */ @Override public boolean equals(Object o) { return false; } /** * Helper method for the equals method * @param node1 the node of the first bst * @param node2 the node of the second bst * @return whether the two trees contain * identical data stored in the same structural * position inside the trees */ private boolean equals(Node node1, Node node2) { return false; } /***MUTATORS***/ /** * Inserts a new node in the tree * @param data the data to insert */ public void insert(T data) { } /** * 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 * in which to insert */ private void insert(T data, Node node) { } /** * Removes a value from the BST * @param data the value to remove * @precondition !isEmpty() * @precondition the data is located in the tree * @throws NoSuchElementException when the * precondition is violated */ public void remove(T data) throws NoSuchElementException{ } /** * Helper method to the remove method * @param data the data to remove * @param node the current node * @return an updated reference variable */ private Node remove(T data, Node node) { return null; } /***ADDITIONAL OPERATIONS***/ /** * Prints the data in pre order * to the console */ public void preOrderPrint() { System.out.println(); } /** * Helper method to preOrderPrint method * Prints the data in pre order * to the console */ private void preOrderPrint(Node node) { } /** * Prints the data in sorted order * to the console */ public void inOrderPrint() { System.out.println(); } /** * Helper method to inOrderPrint method * Prints the data in sorted order * to the console */ private void inOrderPrint(Node node) { } /** * Prints the data in post order * to the console */ 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) { } }
Lab 6 Test File:
import java.util.NoSuchElementException; /** * BSTTest.java * @author parrishj * CIS 22C, Lab 6 */ public class BSTTest { public static void main(String[] args) { BST<Integer> intBst = new BST<Integer>(); BST<Double> doubleBst = new BST<Double>(); BST<Character> charBst = new BST<Character>(); System.out.println("**Integer BST Tests**\n"); System.out.println("Should be empty (true): " + intBst.isEmpty()); System.out.println("Size of an empty tree (0): " + intBst.getSize()); System.out.println("Height of an empty tree, i.e. root is null (-1): " + intBst.getHeight()); intBst.insert(10); System.out.println("Inserting 10. 10 should be root: " + intBst.getRoot()); System.out.println("Inserting 22, 12, 41, 17, 68..."); intBst.insert(22); intBst.insert(12); intBst.insert(41); intBst.insert(17); intBst.insert(68); System.out.println("InOrderPrint: Should print out 10 12 17 22 41 68:"); intBst.inOrderPrint(); System.out.println("PreOrderPrint: Should print out 10 22 12 17 41 68:"); intBst.preOrderPrint(); System.out.println("PostOrderPrint: Should print out 17 12 68 41 22 10:"); intBst.postOrderPrint(); System.out.println("Should not be empty (false); " + intBst.isEmpty()); System.out.println("10 should still be root: " + intBst.getRoot()); System.out.println("Minimum should be 10: " + intBst.findMin()); System.out.println("Maximum should be 68: " + intBst.findMax()); System.out.println("Size should be 6: " + intBst.getSize()); System.out.println("Height should be 3: " + intBst.getHeight()); System.out.println("Searching for 20 (false): " + intBst.search(20)); System.out.println("Searching for 17 (true): " + intBst.search(17)); System.out.println("Removing 17..."); intBst.remove(17); System.out.println("Searching for 17 (false): " + intBst.search(17)); System.out.println("InOrderPrint: Should print out 10 12 22 41 68:"); intBst.inOrderPrint(); System.out.println( "Copying the tree..."); BST<Integer> intBstCopy = new BST<Integer>(intBst); //copying intBst System.out.println("InOrderPrint: Copy should print out 10 12 22 41 68:"); intBstCopy.inOrderPrint(); System.out.println("Two copies are equal (true): " + intBstCopy.equals(intBst)); System.out.println("Testing for deep copy...Removing 10 from copy..."); intBstCopy.remove(10); System.out.println("InOrderPrint: Copy should print out 12 22 41 68:"); intBstCopy.inOrderPrint(); System.out.println("InOrderPrint: Original should print out 10 12 22 41 68:"); intBst.inOrderPrint(); System.out.println("Copy size (4): " + intBstCopy.getSize()); System.out.println("Original size (5): " + intBst.getSize()); System.out.println("Two copies are equal (false): " + intBstCopy.equals(intBst)); System.out.println("\n\n**Character BST Tests**\n"); System.out.println("Inserting D, A, C, S, B, P..."); charBst.insert('D'); charBst.insert('A'); charBst.insert('C'); charBst.insert('S'); charBst.insert('B'); charBst.insert('P'); charBst.insert('Z'); System.out.println("InOrderPrint: Should print out A B C D P S Z:"); charBst.inOrderPrint(); System.out.println("PreOrderPrint: Should print out D A C B S P Z:"); charBst.preOrderPrint(); System.out.println("PostOrderPrint: Should print out B C A P Z S D:"); charBst.postOrderPrint(); System.out.println("Should not be empty (false); " + charBst.isEmpty()); System.out.println("Root should be D: " + charBst.getRoot()); System.out.println("Minimum should be A: " + charBst.findMin()); System.out.println("Maximum should be Z: " + charBst.findMax()); System.out.println("Size should be 7: " + charBst.getSize()); System.out.println("Height should be 3: " + charBst.getHeight()); System.out.println("Searching for Z (true): " + charBst.search('Z')); System.out.println("Searching for D (true): " + charBst.search('D')); System.out.println("Searching for Q (false): " + charBst.search('Q')); System.out.println("Checking 3 cases of remove...."); System.out.print("Removing Z (easy case): "); charBst.remove('Z'); charBst.inOrderPrint(); System.out.print("Removing C (medium case): "); charBst.remove('C'); charBst.inOrderPrint(); System.out.print("Removing D (hard case): "); charBst.remove('D'); charBst.inOrderPrint(); System.out.println( "Copying the tree..."); BST<Character> charBstCopy = new BST<Character>(charBst); //copying intBst System.out.println("InOrderPrint: Copy should print out A B P S:"); charBstCopy.inOrderPrint(); System.out.println("Testing for deep copy...Inserting Q in the copy..."); charBstCopy.insert('Q'); System.out.println("InOrderPrint: Copy should print out A B P Q S:"); charBstCopy.inOrderPrint(); System.out.println("InOrderPrint: Original should print out A B P S:"); charBst.inOrderPrint(); System.out.println("Copy size (5): " + charBstCopy.getSize()); System.out.println("Original size (4): " + charBst.getSize()); System.out.println("\n\n**Testing error messages**\n"); try { System.out.println("Error for getRoot. Tree is empty."); doubleBst.getRoot(); } catch (NoSuchElementException e) { System.out.println(e.getMessage()); } try { System.out.println("Error for remove. Element not found."); charBstCopy.remove('Z'); } catch (NoSuchElementException e) { System.out.println(e.getMessage()); } try { System.out.println("Error for remove. Tree is empty."); doubleBst.remove(3.5); } catch (NoSuchElementException e) { System.out.println(e.getMessage()); } try { System.out.println("Error for findMin. Tree is empty."); doubleBst.findMin(); } catch (NoSuchElementException e) { System.out.println(e.getMessage()); } try { System.out.println("Error for findMax. Tree is empty."); doubleBst.findMax(); } catch (NoSuchElementException e) { System.out.println(e.getMessage()); } } }
What to Submit
How You Will Be Graded
|