(JAVA)

Part one:

In this assignment you will create a tree that can store sentences. Each node stores a single word and may have 0 to N child nodes. The root node is empty and does not store any value. The add(..)method accepts a single sentence as String and breaks it up into words *at each space. These words are then inserted into the tree such that they define a path starting at level 2. There is no limit to the number of levels a tree can have.

In more detail: The method add(..) splits the sentence up by space into N words. These words are then inserted into the tree consisting of potentially existing nodes and newly created nodes. That is, the algorithm will match a nodes value at level 1 to word 0, then match a child of the existing node to word 1, etc. until no match is found. At this point, new nodes are created as a descendant path for each following word in the sentence.

*a word in this case consists of any characters other than space and may include symbols

WordNode.java:

Using class diagram:

WordNode

word: String

children: List

+isLeaf(): boolean

TextTree.java: According to the following class diagram:

TextTree

-root: WordNode

+add(sentence: String): boolean

+contains(sentence: String): boolean

+height(): int // returns the height of the tree

+size(): int // returns the number of nodes +iterator(): Iterator // returns an instance of LeafIterator (see below)

Part two:

LeafIterator.java: Implement a class called LeafIterator which implements java.util.Iterator. The class has the following constructor and two methods: LeafIterator(WordNode root): Initializes the iterator with the given root node boolean hasNext(): checks if another leaf exists in the tree String next(): advances the iterator to the next leaf and returns its word value Now, the TextTree class must implement java.util.Iterable and override the iterator() method which simply creates and returns an instance of LeafIterator.

You may use a Stack or Queue for this iterator. However, the iterator should skip any non-leaf nodes. You may check for leaf vs non-leaf nodes inside the hasNext() method of the WordNode class.

Part three:

Run.java: Create a new class called Run. Create a new TextTree in the main method and add multiple sentence, some of which start with the same words, and some that do not start with the same words. Test the add, contain, size, height methods. Use a for-each loop to iterate over the trees leaves.