WordTree Data Structure

Here we define a special kind of rooted tree that we use to efficiently index words by storing their prefixes. The main property of this tree is that each edge corresponds to a character. Thus the path from the root of the tree to any node in the tree defines a string. The string defined by each node is a prefix of all strings defined by the descendents of that node.

Below is an example tree. It contains the following words: a, and, ax, dog, door, dot. You will note that the dashed nodes correspond to prefixes in the tree (an, d, do, doo) that are not in our list of words. The tree must also keep track of this distinction by storing for each node whether it corresponds to a word or not.

Note that if C is the set of all possible characters defined at the edges, then each node can have at most k = | C | children, where the | C | notation just means the number of elements in set C.

What You Need To Do

Read the provided code (WordTree.java, A3TesterPosted.java), including the comments which explain what the various methods do. This will take you some time, so go slow and read the code carefully. Note that the WordTree class has a private inner class TreeNode.

For the WordTree class, fill in the missing code for the following methods:

- createChild(), toString() for the inner class TreeNode
- getPrefixNode(), insert(), contains(), getListPrefixMatches()

We suggest you implement them in the order listed above. To get started, you may wish to add a main() method to the WordTree class. Eventually you should move on to using the Tester file. Don't forget to delete the main method when you submit !

You may only use Java String methods length() and charAt(). In particular, do not use String searching methods such as String.startsWith(), String.substring(), etc. The point of the assignment is for you to organize and compare strings using this tree data structure.

Only add code in the area where it says to add code. The grader may be sensitive to any changes that you make outside that area. Any helper methods that you wish to write should be added at the end of the WordTree.java file.

Note that all methods and also the inner class have been given the public access modifier. This was done to simplify grading. As you will learn later in the course, typically one does not make all methods public.

Attachment:- Java file.rar