TrieTest.java file
Trie.java file
Your task in this assignment will be to implement a trie class in Java (Trie.java), which will support methods for constructing a trie, as well methods that query the trie for information about the file after the trie has been constructed In term of the implementation for this project, we will think of a trie a structure we update as we scan through a file, adding (or updating the frequencies) of the nodes as we observe new words. Your Trie.java class should support the following methods: . TrieO: Construct an "empty" trie, which just contains a root node. void addWord (String word): Adds the word word to the trie, or increments the frequency of the word by one if it already exists in the trie. You may assume that word only contains lowercase letters. . int wordFrequency(String word): Return the number of times the word word ap- String kthWord(int): Returns the string that, if we were take the list of unique words in the from the file and sort them alphabetically, would be at the kth position of this list (where the first word in the list is at position 1). For example, the sorted sequence of unique words from our earlier example is: a all and are fan fanny frank fred of and so kthWord (5) would return "fan" Starting Code and Submission On Canvas, there are three files you'll use to start your project: TestTrie.java, Trie.java, and alice.txt (which is a .txt file of the Lewis Carrols Alice's Adventure in Wonderland) To set up your project, create a project in NetBeans called Test Trie. Then use TestTrie.java as the project main file, and then add Trie.java to the testtrie package folder. alice.txt should be placed in the top directory of the project (it's fine to place it somewhere else, but you'll have to change the path of the file in TestTrie.java in order to run the tests) Once you've implemented your trie class in Trie.java, you should be able to run TestTrie.java as is (i.e., you should not be modifying this file to make things work). There are ten tests in the file, which each simply make a call to either wordFrequency or kthWordO and prints the result to standard out. The correct outputs are given in comments next to the function cal: Please submit your Trie.java file on Canvas (we will use Canvas for submission of code files). There's no need to subit TestTrie.java or alice.txt; if you have additional .java files, submit them (along with Trie.java) in a compressed folder; however, I'll also note that for this assignment, I'd prefer that the entire implementation is written in Trie.java package trietesti import java.util.*; /Implement this class/ public class Trie t Construct an empty Trie with just a root node. t/ public Trie() Adds a word to the trie (or increases its frequency by one if it already exists in the trie) *eparam word - word to add to the trie. t/ public void addWord (String word) @param word query word to be searched. *return - number of times word appears in file *represented by the trie. public int wordFrequency (String word) @return Return the kth word in the sorted sequence where the first unique word is at position 1. words in the file). *of unique words that exist in the file/trie, *(returns null if k exceeds the number unique public String kthWord (int k)
