|
Bill Teter email: william.teter@plattsburgh.edu |
|
|
Lab 12 and 13 This lab has two parts. In the first you will build a generic binary search tree as specified in the SortedTree<T> interface that is in the public/lab12 directory. In the second you will computed the average height of all binary search trees of size n where n is a command line parameter between 1 and 9. (Since the complexity of your code will be n! any n larger then about 9 will take too long to run and use too much memory. The first part of the lab is due May 8, the second on May 15. Specifications for lab 12 Copy the SortedTree interface, Callback interface and Printer class into your lab12 directory. Copy the BinaryTree class from lab 11 into your lab 12 directory. Rename the class BST.java. BST should be generic <T extends Comparable <? super T>> and implement SortedTree<T>. Begin to edit BST.java by removing unnecessary code. Leave the inner class called Node. The only public methods in BST.java should be those in the SortedTree interface. You will find the inOrder() traversal code is in your texts pp 420 and 430. Write a test program that inserts n (different) random numbers between 0 and 99 where n is a command line argument. The output of your test program should be the size of the tree, the height of the tree and the list of data stored in the tree as given by an inOrder traversal. Your test program should also invoke the find method. Try to find 50. Sometimes it will be there, sometimes not. Specifications for lab13 Copy the Sequences class from public/lab13 into your lab13 workspace. Change the class name and static method name from "sequences" to "permutations". I wrote this Sequences class to compute the set of all sequences that can be formed from the characters in a given string for the Scrabble assignment (lab7). By removing one line from the Sequences code you can make the code compute the set of strings consisting of all permutations of the characters in the string parameter to the permutations() static method. copy BST and related classes from lab12 into your lab13 workspace. Write a program called BSTTest.java that takes a single command line argument that is an integer between 1 and 9 and generates all the binary search trees containing the numbers {0, 1, .. n} and prints the average height of these trees. Since n is no larger than 9 we can use the string "01234..n" as the parameter to permutations() method to obtain the set of all permutations of {0 ..n}. Each permutation generates a binary search tree by inserting the digits one at a time left to right. Assuming each permutation is equally likely, we compute the average height of all binary search trees of size n+1 by averaging the heights of the trees that are produced. Print this average. |