Background:

Lab 8 will allow you to practice recursive Java routines as well as developing a class from scratch. You will re-use (and extend) the Word class from Lab 4 as you implement a binary search tree of words.

What You'll Need

Download the lab8.zip file from the 15-111 course web site. Unzip the file and you should see the following:

• dictionary.txt - a datafile with 172714 words in random order
• words.txt - a much smaller datafile (21 words) to test things with
• BinaryNode.java - like the private inner Node class that the MyLinkedList class used, except it has two self-references, to a left and right instead of just one to the next Node. It also allows for the node to keep track of its level, should you find that useful.

Assignment

For this assignment, we're going to build a Binary Search Tree of words (we'll turn it into a REAL TextTwist helper for the next assignment). You'll want to model your Binary Search Tree class on the linked list class we developed over the last few weeks and on the code from lecture.

You will be implementing a WordTree class that uses BinaryNode to implement a Binary Search Tree of Words. Your WordTree class must implement the following public methods (its interface):

• WordTree() - a default constructor
• WordTree(BufferedReader file) - constructor from a file of words (one per line)
• void insert(Word w) - inserts a Word in the tree (using the unsorted "normal" word as the key)
• BinaryNode find(Word w)
• void delete(Word w) - deletes the Word from the tree (Extra Credit). Be careful with respect to how this interacts with the level of the node!
• void inOrder() - prints an inorder traversal of the WordTree
• void preOrder() - prints a preorder traversal of the WordTree
• String toString() - returns a string that represents a level-order traversal of the WordTree. The levels MUST be identified (i.e., Level 0, then words at level 0; Level 1, then words at level 1, etc.) and separated. If you attempt the delete code and mess up the level info, you will not get full extra credit for delete.
• public static void main(String[] args) - to test your code. It must allow the user to specify the input file repeatedly until a valid file is provided.

You will need to modify the Word class to implement the Comparable interface (since we have to compare Words). This means you must implement the compareTo(Object o) method in your Word class and add implements Comparable to the class declaration. The compareTo method is invoked by a Comparable object, and takes another object as a parameter and returns an int. When called as (Comparable) x.compareTo(y), the method returns a negative integer if x < y, 0 if they're equal, and a positive integer if x > y. FYI, Strings are comparable.

You should write this code incrementally and test it on words.txt before trying the larger file. Note, for this assignment, we're not filtering words to be inserted. Every word in the file, regardless of length, should be inserted in your WordTree.

A discussion of the design and demo of the solution will take place in Thursday's lecture.

Handing in your Solution

Use the Intro Programming dropoff form to submit your zip file.