In this program, we are going to modify the linked (non-array) binary tree so th

Question

In this program, we are going to modify the linked (non-array) binary tree so that it acts as a general tree that stores a dictionary of words. Assuming that words are stored as sequences of characters, the letters car be treated as being in certain positions, just like they are in strings. For example, the word HAT has 3 letters, H in position zero, A in position one, and T in position 2. The words must be stored where each node's right pointer points to letters in the same position in a word (making a 'row' of letters that are in that position) while left pointers move to the next 'row' of letters that might store the next letter in the word. Here's an example that stores the words CAT, CATCH, CATS, and COP. Modifications to the BinaryTrce class. Rename the class so that it is called "DictionaryTree". Change elementType into type char. Add a bool called 'wordEnd' to the node structure. This will be set to true when the node constitutes the end of a word. In the example on the right, the nodes for T, 'H', 'S', and would be marked as ends of words. Add two modules: one that loads the words from "DictionaryWords.txt" into the tree structure as described, and another that finds words in the dictionary tree. The word finder module must accept a string class object as a parameter and return a bool based on what it discovers. If the string is found in the dictionary and is a word, return true. Return false otherwise. This module may assume that all letters will have been converted to lowercase. Driver Details: Load the words from the file "dictionary.txt" into your tree, then ask the user to enter a word to see if it is in the dictionary. Find out if the user-entered word is in the dictionary and report the results to the screen. Repeat until the user enters "-" (two hyphens). Remember that the words entered here will not be found if they contain uppercase letters.

Explanation / Answer

ifndef DICTIONARY_H #define DICTIONARY_H #include using namespace std; typedef const char* cstr; int toLower(char c) { //Return a lowercase letter if its within A-Z (65-90) on the ASCII table; //Otherwise return 'c' as it is (don't bother with non-alphabetical characters). return (c > 64 && c < 91) ? c+26 : c; } class dictionary { private: struct node { char letter; string definition; node* alphabet[26]; explicit node(); explicit node(const node& nodeCopy); ~node(); node& operator = (const node& nodeCopy); void clear(); void copy(const node& src); }; node mainNode; int getArrayIndex(char c); node* iterateToNode(cstr nodeName); public: dictionary() {} dictionary (const dictionary& dictionCopy) {mainNode.copy( dictionCopy.mainNode );} ~dictionary() {} dictionary& operator = (const dictionary& dictCopy); cstr getDefinition (cstr word); void defineWord (cstr word, cstr inDefinition); bool knowWord (cstr word); bool knowDefinition (cstr word); void addWord (cstr word); void clear () {mainNode.clear();} }; //----------------------------------------------------------------------------- // Node Structure //----------------------------------------------------------------------------- dictionary::node::node() : letter(0), definition("") { //NULL-ify all of the elements in the array int iter(26); while (iter--) alphabet[iter] = 0; } dictionary::node::node(const node& nodeCopy) { copy(nodeCopy); } dictionary::node::~node() { clear(); } dictionary::node& dictionary::node::operator = (const node& nodeCopy) { copy(nodeCopy); return *this; } void dictionary::node::clear() { int iter(26); while (iter--) { if (alphabet[iter]) { delete alphabet[iter]; alphabet[ iter ] = 0; } } } void dictionary::node::copy(const node& src) { clear(); letter = src.letter; definition = src.definition; int iter(26); while (iter--) { if (src.alphabet[ iter ]) { alphabet[ iter ] = new node; //memory-safe operation. The destination node has already been cleared alphabet[ iter ]->copy(*src.alphabet[ iter ]); //begin recursive awesomeness! } } } //----------------------------------------------------------------------------- // Utilities //----------------------------------------------------------------------------- dictionary& dictionary::operator =(const dictionary& dictCopy) { mainNode = dictCopy.mainNode; return *this; } dictionary::node* dictionary::iterateToNode(cstr nodeName) { int pos(0), index(0); node* nodeTracker(&mainNode); //dictionary iterator do { index = getArrayIndex( nodeName[pos] ); if (index == -1 || !nodeTracker->alphabet[ index ]) return 0; nodeTracker = nodeTracker->alphabet[index]; ++pos; } while (nodeName[ pos ]); //end the loop when a null-termination is reached return nodeTracker; //return the position of the requested node } int dictionary::getArrayIndex(char c) { //make sure the letter in question actually is a letter if ((c < 'a') && (c > 'Z') || (c < 'A') || (c > 'z')) return -1; return (c < 'a') ? c - 'A' : c - 'a'; //convert all uppercase letters to lowercase (See asciitable.com) //get the index of the next letter in dictionary::alphabet[] } //----------------------------------------------------------------------------- // Definitions //----------------------------------------------------------------------------- cstr dictionary::getDefinition(cstr word) { node* nodeTracker( iterateToNode(word) ); return (nodeTracker) ? nodeTracker->definition.c_str() : ''; } void dictionary::defineWord(cstr word, cstr inDefinition) { node* nodeTracker( iterateToNode(word) ); if (nodeTracker) nodeTracker->definition = inDefinition; } bool dictionary::knowWord(cstr word) { node* nodeTracker( iterateToNode(word) ); return (nodeTracker) ? true : false; } bool dictionary::knowDefinition(cstr word) { node* nodeTracker( iterateToNode(word) ); return (nodeTracker && nodeTracker->definition.size()) ? true : false; } void dictionary::addWord(cstr word) { int pos(0), index(0); node* nodeTracker(&mainNode); //dictionary iterator do { index = getArrayIndex( word[ pos ] ); //get the index of the next letter in dictionary::alphabet[] if (index == -1) return; if (nodeTracker->alphabet[ index ] == 0) { nodeTracker->alphabet[ index ] = new node; //add a new word to the dictionary if possible nodeTracker->letter = word[ pos ]; } nodeTracker = nodeTracker->alphabet[index]; //move to the next letter in dictionary::alphabet ++pos; } while (word[ pos ]); //end when a null-termination is reached } #endif /* DICTIONARY_H */

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.