A trie is a very specialized tree that both is extremely efficient at storing words and also is incredibly fast to access. You can find a word in a trie in itme proportional to the length of the word, no matter how large the trie.
Each node of a trie has a flag to indicate a word is complete
and an array of links corresponding to all the possible characters in the
word. It would look like this:
class
trie
{
private:
bool done; // true when end of a word is reached
trie * links[256]; // list of character links
public:
// constructs a node
trie() { done=false; for(int index=0;index<256;index++) links[index]=NULL; }
// deletes a set of words
~trie() ;
// insert a word into the trie starting with the specified index
void insertWord(char word[],int index=0);
// find a word in the trie starting with the specified index
bool findWord(char word[], int index=0);
}; // end trie
If you were to store the word and in a trie you would add a link indexed by character ‘a’. Then the ‘n’ link and the ‘d’ would be stored. If you would install the words ant and art you would get a trie diagrammed as shown:
Adding the word anthor leads to a diagram like this:
You need to add code for insert word and find word to the class.