C++. Please help. I'm stuck with my homework

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

These will be a template classes:

template

class TreeNode

template

class BinarySearchTree

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 BinarySearchTree;

// TreeNode class

template

class TreeNode

{

friend class BinarySearchTree;

// the rest of the TreeNode classs declaration goes here

};

// BinarySearchTree class

template

class BinarySearchTree

{

// Your BinarySearchTree goes here

};

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.

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 an 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 that uses the find member function:

// prototype

void processFound(const std::string &item);

// 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.

Note that the function you pass to find is either a stand-along 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.

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);

Your update function 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:

// declaration of binary tree

BinarySearchTree tree;

tree.insert("555-122-3333", &update);

The update function is called if item "555-122-3333" already exists in the tree.

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.

Constructors and destructor

You will need a default constructor, a copy constructor, and a 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. Make sure your destructor removes any remaining items from the tree.

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 35,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.

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 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 BinarySearchTree class 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)

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. Note that 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

aadlls

You will need processing similar to the above in your Word class. You can create the class with a

different name if desired.

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? The default behavior of insert is to replace the existing entry with a new entry. So, by default, the last one of these 4 words that are in the input text file would be word that is found.

You need to update your Word class (or whatever you called it) to support multiple words for one key.

You could then use the 2nd version of the insert to have it call a function you write. You could them update the found entry and add any new words to it.

You would do this by changing your word class to use an array or a std::vector to allow more than one word to be mapped to a key. If you use an array just create it with a maximum of 10 elements. Make sure your Word class does not try to add more than 10 entries to the array. If you use the std::vector you can support any number of duplicates for a given keyword.

Add support to your Word class to allow multiple words to be associated with one key. This will allow you to display multiple solutions. Allow a maximum of 10 entries if you are using an array.

Here is some sample output:

Enter a word to unscramble: sdie[Enter]

The scrambled word sdie maps to words: side dies ides desi

There are some sample scrambled words you can try out. These are in file scambled_words.txt as follow:

posigs

lubyl

daync

lycreg

nedrt

esege

oypret

gneedl

veecrl

dohysd

genada

puxeld

sivent

cnisek

diwmel

roolc

gropn

lewkye

reapo

godde

knuhrs

mahwrt

kojyec

nukhc

caykw

trepwe

natds

bireb

xlaeeh

orupto

teedct

gonyu

nopyh

rufian

lazwt

neaar

yeddab

somsco

trolma

grite

wrisl

mripte

bkirc

lirec

goracu

farotm