Using Java implement the following data structures and assoc

Using Java implement the following data structures and associated algorithms.

Tries

A Trie is a type of Tree that can be used to efficiently represent a set of strings. Tries can also be used to implement Dictionaries where the keys are strings. The edges in a Trie represent characters. The sequence of edges on a path from the root to another node represents the characters, in order, in a string (if that string was inserted into the Trie). Each node stores pointers to its children and a boolean value indicating if the node terminates a path that represents a string inserted into the Trie. The figure below shows the Trie built from the set of strings on the left. In the figure below the path from the root to “act” follows the edges labeled a-c-t, in the set of strings shown on the left. Note that the strings are not actually stored at the nodes (it’s shown that way for illustrative purpose) but they can be reconstructed from the sequence of edges using a preorder traversal of the Trie.

In this project you will implement a simplified version of a Trie. Specifically:

The Trie must be implemented using a linked node implementation where each node stores (1) an array of pointers (or references, if using Java) to its child nodes and (2) a boolean flag indicating if the node represents the end of a path that represents a string in the Trie.

For simplicity, you can make the following assumptions:

1. All strings will are lower case

2. All strings will consist of ASCII characters

3. All strings will contain alphabetical characters only (a-z)

4. All nodes store a fixed-sized array of pointers to child nodes (specifically, 26, one for each lowercase ASCII character).

Each bucket of the child node pointer array is mapped to a corresponding ASCII character. For example, if you name the node’s child pointer array children then children[0] will represent the edge for the character ‘a.’ If such an edge exists then there will be a pointer to a child node. If no such edge exists then children[0] will store a null pointer. The same is true for the edge

representing the character ‘b’ (stored at children[1]), character ‘c’ (at children[2]), etc. Note that the above figure does not follow this scheme, but the figure below does.

In this project you will implement a Trie data structure and the following algorithms:

InsertString(String str) – Inserts a new String str into the Trie. The Trie is initially empty. Note that, as you insert the characters of str that some of the rquired nodes may already exist. As you are traversing the Trie (according to the characters of str) you may need to add new nodes into the Trie or you may be able to reuse nodes that already exist.

For example, if you insert “and” after you inserted “ant” then nodes and edges for the “a” and “n” already exist and only an edge“d” will need to be inserted as a link to the appropriate child of “n.” Similarly, if you try to insert the word “an” after “ant” and “and” have been inserted then the node terminating the path with the edges “a” and “n” already exists and the only operation required is to switch the node from not representing a word to representing a word.

StringExists(String str) – Returns a boolean value indicating if the String str is stored in the Trie.

PrintStrings(String str) – Prints all of the Strings inserted into the Trie to standard output. This requires a preorder traversal of the tree. The preorder traversal must be implemented using the stack data structure described below.

Stacks

The PrintStrings operation will require a preorder traversal of the Trie. While this procedure could be implemented recursively, it is often implemented iteratively using a Stack. You will implement an array-based stack called ArrayStack to support PrintString’s preorder traversal of the Trie. ArrayStack will consist of the following operations: push(), pop(), top(), and isEmpty(). You cannot assume that the ArrayStack only stores pointers/references to Trie nodes, as you will also need a way to keep track of the current String. One option is to have the stack store entries that consists of a TrieNode and a String storing the characters on the path from the root to the current node. The array-based stack will start at some initial minimum size and grow/shrink as elements are pushed or popped. This should be done in an efficient way (i.e., don’t create a new array that is one size larger than the previous array when a new element is pushed onto the stack).

Test Cases

These must be run automatically by your program. Your program will take no user input.

Insert the following Strings into the Trie, in the following order: ant, cat, zoo, zone, bat, band, bean, fish, fishing, banana, catch, cannot, can, find, fix, any, zone, zoos, zoo

Determine if the following Strings are in the Trie: fin, find, baton, bat, ban, catching, ant, zones, can

Print all of the words stored in the Trie using the PrintStrings operation.

Example Code (in Java, untested, not compiled)

public class Trie {

private TrieNode root = null;

public Trie() {

}

public void insertStr(String str) {

}

public boolean strExists(String str) {

}

public void printStrs() {

}

}

public class TrieNode {

private boolean strInTrie = false;

private final TrieNode [] children = new TrieNode[26];

public TrieNode() {

}

}

public class ArrayStack {

private ??? [] arr;

public ArrayStack() {

}

public void push(???) {

}

public TrieNode pop() {

}

public TrieNode top() {

}

public boolean isEmpty() {

}

}

Solution

Sample Output :

fin exists? :false
find existis? :true
baton existis? :false
bat exists? :true
ban exists? :false
catching exists? :false
ant exists? :true
zones exists? :false
can exists? :true
Printing all words.
zoo
zoos
zone
fix
fish
fishing
find
can
cat
catch
cannot
bean
bat
band
banana
ant
any