Part 1
Part 1 will test the binarySearchTree class you will create.
Part 2 will test the word search application you create that uses the binarySearchTree class.
In part 2 you will be creating a program that allows you to quickly solve Jumble or Scram-lets types of puzzles. To do this be using a binary search tree you will be creating. Your application will read in a list of words (over 35,000). You will sort the letters of each word to create a key. You will then add the key (and the word) to the tree (as one instance of a class called word).
Example:
The word you read in from the file is the word "Binary". You need to create a key from this. The key will be the word folded to lower case and ordered by its letters. So the word Binary first gets folded to lower case (binary) and then ordered by letter order - abinry. The key is abinry and the word is Binary. You need to create a class for this item ( call it word). The word contains both the key (abinry) and the word text (Binary). This is added to the binary search tree in key order.
Actually the word text, "Binary" in the above example, needs to be added to a std::vector< std::string>. There may be more than one word that maps to a given key. As an example, the key "abekr" maps to words "break", "baker", and "brake".
Once the dictionary of look up words has been build your application will prompt for a jumbed word. You will fold the jumbled word to lower case and sort the letters in the word. This will be what you look up in your dictionary of lookup words. If it is found you get the word text and that is your word unscrambled.
Example 1:
You type in Arbiny. This is folded to lower case (arbiny) and sorted (abinry). You look up the key abinry and it finds the word text Binary. So arbiny maps to Binary
Example 2:
You type in rekba. This is folded to rekba (so it isn't changed since it is already in lower case). You then sort the string and get abekr. The vector for the word object for abekr will contain three entries - break, baker, and brake.
This is part 1 - Build the binarySearchTree
binarySearchTree and treeNode classes
First you need to create and test the binarySearchTree class. The binarySearchTree will contain treeNode objects. These are both template classes.
template< class DataType>
class treeNode
{
// class goes here
};
template< class DataType>
class binarySearchTree
{
// class goes here
};
If you want to make binarySearchTree a friend class of the treeNode you will need a forward declaration of the binarySearchTree. So your header file may look similar to the following:
// forward declaration of the template class binarySearchTree
template< class DataType>
class binarySearchTree;
// treeNode class
template < class DataType>
class treeNode
{
friend class binarySearchTree;
// the rest of the treeNode class declaration goes here
};
// binarySearchTree class
template < class DataType>
class binarySearchTree
{
// Your binarySearchTree goes here
};
You can use the listNode class as a template for the treeNode class. You will need to change the next and prvious behaviors and have left child and right child pointers / member functions instead.
The binarySearchTree class needs to implement the following member functions:
bool empty() const
The empty member function will return true if the binary tree is empty.
std::size_t size() const
Returns the number of items in the binary tree.
void print() const;
Display the contents of the binary tree in order by key (inorder traversal). Whatever is being stored in the binary tree will have to have overload the operator<< operator.
Output each element in the tree on a line by itself. Do not include any extra whiltespace .
void debug(std::ostream &out) const;
Display the contents of the binary tree for debugging purposes. Use whatever traversal algorithm makes sense to you. Make sure you output the left and right pointers from the treeNode. Do this for all nodes in the binary tree. Note, this could be a lot of output for a binary tree that has hundreds or thousands of entries. You may want to output this to a file (that is, you may want to pass a std::ofstream to the debug member function). Since std::ostream is a parent to std::ofstream you can do this and you should not change the signature of the debug member function. See the debug code provided with assignment 3 for help in writing this debug member function.
bool find(const DataType &searchItem, void (*foundNode)(const DataType&));
The first parameter passed to the find member function is the item we are looking for. The second parameter is the address of a function that will be called if the searchItem is found in the binary tree collection. The found item is passed to the function. If the item is found, the function is called, and the find member function will return true. If the item is not found, the function is not called, and find returns false.
Here is an example of your application code that would be used to make use of the find member function. Notes this code would be in your application program (main as an example) and is not part of the binarySearchTree ckass,
Here is an example that uses the find member function:
// assume this is your application code:
// function prototype to be called when an item if found in the binary search tree
void processFound(const std::string &item);
…
int main()
{
...
// declaration of binary tree
binarySearchTree tree;
…
bool result = tree.find("555-122-3333", &processFound);
// result will be true if item "555-122-3333" was found and
// the processFound function was called.
...
return 0;
}
void processFound(const std::string &item)
{
cout << "The item " << item << " was found in the tree" << endl;
}
Note: The function you pass to find is either a stand-alone function (such as processFound above) or a static member function in a class. It cannot be a regular member function, it has to be a static member function.
The function passed to the find member function is used by the application using the binarySearchTree class. It allows the application using the binarySearchTree a way to get access to the found item in the tree so it can do its application specific processing.
bool erase(const DataType &deleteItem);
The erase member function will remove the specified item from the binary tree (if it finds the entry in the tree) The erase member function will return true if the item was found and removed and false if it was not found.
void insert(const DataType &newItem);
Insert the item into the binary tree. If the entry already exists it should be replaced by the new one.
void insert(const DataType &newItem, void (*duplicateItemFound)(DataType &existingItem, const DataType &newItem));
Insert the item into the binary tree. If the item already exists the duplicateItemFound function will be called. This is the function passed as the 2nd parameter to the insert function. Note this must either be a stand-alone function or a static member function. The signature of the function is as follows (the function name can be different):
void update(DataType &exsitingItem, const DataType &newItem);
In the above example you will replace DataType with the actual type of the object stored in the tree.
Your update function (above) will get a modifiable version of the found item (existingItem) and a const reference to the new item. You can update the existingItem as needed in the update function.
Here is an example using the update function above. This code would be part of your application code and is NOT part of the binarySearchTree class.
// in your application program
// function prototype
void update(std::string &existingString const std::string &newString);
int main()
{
...
// declaration of binary tree
binarySearchTree< std::string> tree;
…
tree.insert("555-122-3333", &update);
...
return 0;
}
void update(std::string &existingString const std::string &newString)
{
cout << "The item " << existingString << " already exists" << endl;
cout << "The new item" << newString << " is ignored" << endl;
}
The update function is called if item "555-122-3333" already exists in the tree.
Note: The update function should not change the key of the item. Doing this could break the ordering of the binary search tree.
Once again, the function passed to insert member function is used by the application using the binarySearchTree. It gives the application access to the item that already exists in the tree, and it gets the item that was being inserted into the tree (but has a duplicate key). This gives the application a way to handle the duplicate entry issue.
void traverse(void (*itemFound)(const DataType& foundItem)) const;
The traverse function will do an inorder traversal of the binary tree. For every item found it will call the itemFound function and pass it a const reference to the found item.
Since the binarySearchTree class does not have an iterator we are going to use the traverse member function to allow application specific code a way to access all of the elements in the tree. Again, an application using the binarySearchTree passes a function to the traverse member function. That application specific function will then get called once for every item in the tree.
Constructors, destructor, and assignment operator
You will need a default constructor, a copy constructor, and a destructor. Make a destructor a virtual destructor.
The copy constructor needs to make a deep copy of the tree. You should be able to use other member functions to do most of the work for you. You should use preorder traversal of the binary tree to get the items from the tree being copied from.
Make sure your destructor removes any remaining items from the tree. The zyBooks text does not talk about the need to delete the objects in the tree. You need to explicitly do this in C++ since we do not have a garbage collector (as you have in Java). Here is some pseudo-code to help you with this:
deleteAll and deleteAll(treeNode *node) pseudo-code
Both of these need to be private member functions in your binary search tree. You can then delete all of the entries with:
deleteAll();
The treeNode needs to be replaced with the treeNode< DataType> syntax.
void deleteAll()
{
deleteAll(root)
root = nullptr
}
void deleteAll(treeNode *node)
{
if (node != nullptr)
{
// delete all nodes to the left
deleteAll(node->left());
node->left(nullptr);
// delete all nodes to the right
deleteAll(node->right());
node->right(nullptr);
// delete the node now
delete node;
numberNodes--;
}
}
You also need an assignment operator. This must also do a deep copy. In addition it has to delete the entries from the binary search tree being copied into. Your assignment operator must check to make sure you are not trying to assign to the same list. You can check this by comparing the this pointer to the address of the tree being copied from. If the addresses are the same your assignment operator should just return back a reference to the this object. You should do a preorder traversal of the nodes for the assignment.
The online materials talk about this.
Other information
You can add other member functions as needed. Make sure you free up any memory you allocate.
You should write stubs for all of the functions as you are creating the classes and then incrementally implement the member functions for the treeNode and binarySearchTree classes. By doing this incremental development you will have a better idea which function is failing (because it is probably the code you just wrote).
Also, make sure you test and fix a member function before you go onto the next one.
Look for opportunities to reuse code you already have in the class to implement other member functions.
Use good formatting in your programs. Use meaningful variable names and comment your code.
You can inline trivial member functions in the treeNode and binarySearchTree classes (trivial being 1 to 5 lines of code).
You must implement all of the member functions shown here. You can implement additional private, and protected member functions if you need them.
Create a header file named binarySearchTree.h that contains your binarySearchTree and treeNode class definitions and any implementation code needed. Include the required header file including any guards needed.
Please write a driver function (main) to test your binarySearchTree class. In the next part you will be creating an application that uses the binarySearchTree and treeNode classes.
You now have all of the code you need to run the tests for part 1. There are 5 tests for part 1. The tests will make use of your binarySearchTree class.
Part 2
This section describes the code you will be writing and submitting for part 2 (the next section in zyBooks). This is the application. You will be using the binarySearchTree you created in part 1.
The tests for the application are in Binary Search Tree (Part 2) - the next unit in zyBooks.
Word Unscrambling Program
Now that you have a working binarySearchTree class you need to create your word unscrambling program. The way this program will work is as follows:
You will be reading a file, "english_words.txt", that contains a number of words (over 30,000 words). You will read in a word and make a copy of it. The copy of the word needs to be folded into lower case (see the std::tolower function in header file cctype. This will take one character and convert it to lower case. You will need to do this for every character in the copy of the word you read in. After you have folded the copy of the word to lower case you need to sort the characters in the string in character order. So if the word is Help you will make a copy of this word (call it key) and fold it to lower case giving you help. Now you sort the characters and you end up with ehlp. Now you have a key, ehlp and the original word Help.
When you read in the values from file "english_words.txt" make sure you use the >> operator to read in the words. If you use getline your program will read in an extra \r at the end of every word and your program will not work properly.
You need to create a class to contain both of these values. You will add an instance of this class to your tree.
For our discussion assume we call this class word. The constructor for the word class will take the word passed to it and determine the key for that word. The resulting word object will contain both the key and the original value for the word.
Assume we can create a word as follows:
word newWord("Help");
The word newWord will have a key of ehlp and a value of Help. We can insert the word item into our binary tree. Assume the tree is defined as follows:
binarySearchTree< word> dictionary;
We can add the word with:
dictionary.insert(newWord);
For insert to work properly you will have to have your word class override operator== and operator< (at the very least). If your binarySearchTreeclass uses comparison operators in addition to these you will need to implement them as well.
For the print and debug member functions in your binarySearchTree class you work you will also need to implement:
std::ostream& operator<<(std::ostream &out, const word &outputWord)
Your operator<< function will be a stand-alone function and is not a member function of word. Create the prototype after the word class definition in the header file word.h. The operator<< should be implemented in the word.cpp file.
Assume the key is dgo and that it maps only to the word dog. The output from operator<< must be:
[dgo, {dog}]
The key abekr maps to three words - break, baker, and brake. The output will be as follows:
[abekr, {break, baker, brake}]
*Hints for doing the sorting of the characters and changing individual characters in a std::string.
Recall that when working with a std::string you can access and update individual characters using either the ``at()``` member function or the subscript operator. Here is an example:
std::string text("Hello");
text[0]= 'h';
std::cout << text << std::endl;
will output
hello
Also, the algorithms header file has a function called std::sort. This required two iterators to sort a collection of values.
The std::string class is a type of collection. You can get an interator to the first character in the std::string by calling the begin() member function. You get the end of the string with the end() member function. Like all other iterators the end() does not give you the last character in the std::string but an indication that you are beyond the end of the string. These two member functions are exactly what you want for the std::sort function.
So you can sort the characters in a std::string as follows:
std::string myText("dallas");
std::sort(myText.begin(), myText.end());
std::cout >> myText >> std::endl;
will output
addlls
back to the application
You will need processing similar to the above in your word class.
Once you have read in all of the words, created your word objects and added them to your binarySearchTree you need to do the main processing for the application.
You need to read in scrambled words and see if they are in your binary tree.
You need to read in the scrambled word and sort the characters of the word into order by characters (you are creating the key for the scrambled word). If that key exists in your tree you now know the word that that key maps to and you have unscrambled the word.
Assume the word "Help" is in the tree with a key of ehlp.
Your program asks for a scrambled word and the user types in: Pelh
Your program should fold this to lower case and sort the letters. The resulting key is "ehlp". When you look for this in your binary search tree it will be found and the resulting word will be Help. You have unscrambled Pelh into Help.
But, what about duplicate words? The scrambled word sdie could map to side, dies, ides and desi. All of these are in the input file. Which one should you keep? You need to have your word class to support multiple words for one key. You will use the 2nd version of the insert to have it call a function you write. You can then update the found word entry and add any new words to it.
Use push_back to add the new words to the end of the std::vector. Recall that the function you provide on the insert will be passed two parameters. The first parameter will be a reference to the actual word entry in the tree. The second parameter will be the word you were trying to insert. Your program will have to add the actual word from the second parameter to the vector of words in the first parameter.
When a word is entered by the user the application needs to look for that word in the dictionary. Your program should use the find that takes a function. This function can either be a stand-alone function or it can be a static function in the word class. Assume this function is named wordFound. The wordFound function will be called if a word is found. You can then output the list of words (separated by spaces) as shown in the sample output.
There are some sample scrambled words you can try out. These are in file "scambled_words.txt".
Here is some sample output. You need to match the output exactly
The text that ends with "[Enter]" is the input data typed into std::cin.
Test of find words
The dictionary has been built with 32194 keys in the dictionary
Word to unscramble (quit-now to stop):
larayed[Enter]
Scrambled word larayed maps to word: already
Word to unscramble (quit-now to stop):
amnprtacegia[Enter]
Scrambled word amnprtacegia maps to word: paramagnetic
Word to unscramble (quit-now to stop):
IBaldArch[Enter]
Scrambled word IBaldArch maps to word: Archibald
Word to unscramble (quit-now to stop):
cainar[Enter]
Scrambled word cainar maps to words: arnica crania carina
Word to unscramble (quit-now to stop):
vaishaniv[Enter]
Scrambled word vaishaniv was not found
Word to unscramble (quit-now to stop):
himnpest[Enter]
Scrambled word himnpest maps to word: shipment
Word to unscramble (quit-now to stop):
quit-now[Enter]
Part 3
You need to add the following member functions to your binarySearchTree class.
You will need to submit a modified assignment4.cpp file that does not use the word class from part 2.
// print to ostream
void print(std::ostream &out) const;
// traverse preorder
void traversePreOrder(void (*itemFound)(const DataType& foundItem)) const;
// traverse outorder
void traverseOutOrder(void (*itemFound)(const DataType& foundItem)) const;
void print(std::ostream &out) const
The current version of print outputs the contents of the tree to std::cout. This one will output to the passed in std::ostream.
The output should be exactly the same as output by the original print, it is only where the content is written to that is different.
void traversePreOrder(void (itemFound)(const DataType& foundItem)) const and void traverseOutOrder(void (itemFound)(const DataType& foundItem)) const
These perform in a similar way to the traverse member function you wrote in part 1. What is different is that you need to call the itemFound function for the values in pre-order or out-order, depending on which version of the traverse is called. The original traverse member function should continue to be in in-order sequence.
The out order traversal will display the values in reverse of the sorted order. The wikipedia entry on tree traversal calls this reverse-in-order.
