CMSC206 Data Structures
Fall 2014

Assignment 6
Due on Tuesday, November 25, 2014

This assignment contains TWO parts. Please read carefully before starting on the assignment.

Part #1: Write a Java prigram that uses the Binary Search Tree data type from class (provided here: BinaryTree, BST) to do the following:

A. Use the add() method to add the following strings to the BST:

1. Cambridge
2. Crapo
3. Your birth place
4. Bryn Mawr
5. Boring
6. Hell
7. Walla Walla
8. Surprise
9. Joseph
10. Romance
11. Mars
12. Nuttsville
13. Rough and Ready
14. Dynamite
15. Good Grief

After adding the above, do a preorder, postorder, and inorder traversal (printing out each node as you visit). Also print out the number of entries in the tree, and its height. You will need to define the three methods: preOrder(), postOrder(), and inOrder() in the binary tree class and then use them.

B. Clear the tree, and print out the number of items and its height. Then add the above towns in ascending order. Print out the resulting tree's size, and height, and also the results of all three tree traversals.

Hand in a complete prinout of your program (you do not have to print out the code/classes already provided) along with the output.

Part#2: Redo Assignment#4 to use 1 entry per town (with a list of all zip codes) and entries stored in a Binary Search Tree (as implemented in the text or in Part#1) using the string TOWN+STATE as the ordering relation.

For demonstrating the correctness of your program, include a printout that shows the output from following queries:

1. Cambridge, MA
2. Crapo, MD
3. Your birth place (if in the US)
4. Bryn Mawr, PA
5. Boring, OR
6. Hell, MI
7. Walla Walla, WA
8. Surprise, NY
9. Joe, Montana
10. Romance, Arkansas
11. Mars, PA
12. Nuttsville, VA
13. Rough and Ready, CA
14. Dynamite, WA
15. Good Grief, Idaho

Additionally, after reading in the input file, your program should print the height of the resulting tree.

The objective here is to compare the performance of your program from Assignment#4. As before, once you have completed the program, extend it to count the number of comparisons needed to answer a query. Then, for the input data above, compute the average number of comparions needed to answer a query, the average number of comparisions needed to answer a successful query, the average number of comparisons needed to answer an unsuccessful query. Next, compare these results to those obtained in Assignment#4. Hand the main program, and sample output(s) showing the correctness of your implementations, and a short narrative based on the results of your comparisions (do this in the context of expected time complexity of the two data structures and the search algorithm(s)).

Back to CS206 Course Materials