C++. At the end, there is an already done code for binarySearchTree.h.

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

#ifndef PROJECT5EC_BINARYSEARCHTREE_H

#define PROJECT5EC_BINARYSEARCHTREE_H

#include

#include

#include

#include

#include

#include

#include

#include

// forward declaration of the template class BinarySearchTree

template

class BinarySearchTree;

// TreeNode classe

template

class TreeNode

{

friend class BinarySearchTree;

private:

// Data members

DataType key; // Binary search tree data item

TreeNode *left;//Pointer to the left node

TreeNode *right;//Pointer to the right node

// the rest of the TreeNode classs declaration goes here

public:

//Default Constructor

inline TreeNode()

{

//key;

left = nullptr;

right = nullptr;

}

//Copy Constructor

inline TreeNode(const DataType &nodeDataItem, TreeNode *leftPtr, TreeNode *rightPtr)

{

key = nodeDataItem;

left = leftPtr;

right = rightPtr;

}

};

// BinarySearchTree class

template

class BinarySearchTree

{

// Your BinarySearchTree goes here

private:

int numberNodes;

TreeNode*root;//Root pointer

public:

BinarySearchTree();

BinarySearchTree(const BinarySearchTree &other);

virtual ~BinarySearchTree();

void destroy(TreeNode* &p);

bool empty() const;

std::size_t size() const;

void print() const;

void debug(std::ostream &out) const;

bool find(const DataType &searchItem, void(*foundNode)(const DataType&));

static void processFound(const DataType &item);

bool erase(const DataType &deleteItem);

void insert(const DataType &newItem);

void insert(const DataType &newItem, void(*duplicateItemFound)(DataType &existingItem, const DataType &newItem));

static void update(DataType &exsitingItem, const DataType &newItem);

void traverse(void(*itemFound)(const DataType& foundItem)) const;

void printTree(TreeNode* node) const;

void copyTree(TreeNode* &copiedTreeRoot, TreeNode* otherTreeRoot);

void deleteFromTree(TreeNode* &p);

void inorder(TreeNode *p) const;

void inorder2(TreeNode *p) const;

};

template

BinarySearchTree::BinarySearchTree()//Default Constructor

{

root = nullptr;

numberNodes = 0;

}

template

BinarySearchTree::BinarySearchTree(const BinarySearchTree &other)//Copy Constructor

{

if (other.root == nullptr) //otherTree is empty

root = nullptr;

else

copyTree(root, other.root);

}

template

BinarySearchTree::~BinarySearchTree() //destructor

{

destroy(root);

}

template

void BinarySearchTree::processFound(const DataType &item) //Static function to use with find function

{

std::cout << "The word/words found are: " << std::endl;

}

template

void BinarySearchTree::destroy(TreeNode* &p) //This will destroy an entire Binary Search Tree

{

if (p != nullptr)

{

numberNodes--;

destroy(p->left);

destroy(p->right);

delete p;

p = nullptr;

}

}

//Pretty self explanatory. Does a deep copy of the tree that is being passed in.

template

void BinarySearchTree::copyTree(TreeNode* &copiedTreeRoot, TreeNode* otherTreeRoot)

{

if (otherTreeRoot == nullptr)

copiedTreeRoot = nullptr;

else

{

copiedTreeRoot = new TreeNode;

copiedTreeRoot->key = otherTreeRoot->key;

numberNodes = numberNodes + 2;

copyTree(copiedTreeRoot->left, otherTreeRoot->left);

copyTree(copiedTreeRoot->right, otherTreeRoot->right);

}

} //end copyTree

//This goes ahead and checks if the BinarySearchTree is empty or not

template

bool BinarySearchTree::empty() const //WORKS

{

if (root == nullptr)

return true;

else

return false;

}

//Gives us the size of the Binary Search Tree

template

std::size_t BinarySearchTree::size() const

{

return numberNodes;

}

template

void BinarySearchTree::print() const//Prints the entire content of the Binary Search Tree

{

if (root == nullptr)

return;

else

{

printTree(root);

}

}

template

void BinarySearchTree::printTree(TreeNode* node) const//Prints one of the entries

{

if (node == nullptr) return;

printTree(node->left);

std::cout << node->key << std::endl;

printTree(node->right);

}

template

void BinarySearchTree::debug(std::ostream &out) const//Prints certain information of the Binary Search Tree

{

const unsigned int ADDRWIDTH = 10;

out << "START DEBUG" << std::endl;

out << "# nodes=" << size() << std::endl;

inorder2(root);

unsigned int count = 1;

//print();

out << "END DEBUG" << std::endl;

}

//Tries to find the entry in the binary search tree

template

bool BinarySearchTree::find(const DataType &searchItem, void(*foundNode)(const DataType&))

{

TreeNode *current;

int count = 0;

bool found = false;

if (root == nullptr)

std::cout << "Cannot search an empty tree." << std::endl;

else

{

current = root;

while ((current != nullptr && !found))//

{

if (current->key >= searchItem)//I want this to test the keys not names

{

found = true;

foundNode(searchItem);

std::cout << current->key << std::endl;

}

else if (current->key > searchItem)

current = current->left;

else

current = current->right;

count++;

}//end while

}//end else

return found;

}//end

template

bool BinarySearchTree::erase(const DataType &deleteItem)//erases a node from the Binary Search Tree

{

TreeNode *current; //pointer to traverse the tree

TreeNode *trailCurrent; //pointer behind current

bool found = false;

if (root == nullptr)

std::cout << "Cannot delete from an empty tree." << std::endl;

else

{

current = root;

trailCurrent = root;

while (current != nullptr && !found)

{

if (current->key == deleteItem)

found = true;

else

{

trailCurrent = current;

if (current->key > deleteItem)

current = current->left;

else

current = current->right;

}

}//end while

if (current == nullptr)

std::cout << "The item to be deleted is not in the tree." << std::endl;

else if (found)

{

if (current == root)

deleteFromTree(root);

else if (trailCurrent->key > deleteItem)

deleteFromTree(trailCurrent->left);

else

deleteFromTree(trailCurrent->right);

}

else

std::cout << "The item to be deleted is not in the tree." << std::endl;

}

} //end deleteNode

template

void BinarySearchTree::deleteFromTree(TreeNode* &p)//delete an entry from the Binary Search Tree

{

TreeNode *current; //pointer to traverse the tree

TreeNode *trailCurrent; //pointer behind current

TreeNode *temp; //pointer to delete the node

if (p == nullptr)

std::cout << "Error: The node to be deleted does not exist." << std::endl;

else if (p->left == nullptr && p->right == nullptr)

{

temp = p;

p = nullptr;

delete temp;

}

else if (p->left == nullptr)

{

temp = p;

p = temp->right;

delete temp;

}

else if (p->right == nullptr)

{

temp = p;

p = temp->left;

delete temp;

}

else

{

current = p->left;

trailCurrent = nullptr;

while (current->right != nullptr)

{

trailCurrent = current;

current = current->right;

}//end while

p->key = current->key;

if (trailCurrent == nullptr) //current did not move;

//current == p->lLink; adjust p

p->left = current->left;

else

trailCurrent->right = current->left;

delete current;

}//end else

numberNodes--;

} //end deleteFromTree

template

void BinarySearchTree::insert(const DataType &newItem)//Insert an organized item into the Binary Search Tree

{

TreeNode *current; //pointer to traverse the tree

TreeNode *trailCurrent; //pointer behind current

TreeNode *newNode; //pointer to create the node

newNode = new TreeNode;

newNode->key = newItem;

newNode->left = nullptr;

newNode->right = nullptr;

if (root == nullptr)

{

root = newNode;

numberNodes++;

}

else

{

current = root;

while (current != nullptr)

{

trailCurrent = current;

if (current->key == newItem)

{

// std::cout << "The item to be inserted is already ";

// std::cout << "in the tree -- duplicates are not " << "allowed." << std::endl;

// std::cout << newItem << std::endl;

update(current->key, newItem);

return;

}

else if (current->key > newItem)

current = current->left;

else

current = current->right;

}//end while

if (trailCurrent->key > newItem)

{

trailCurrent->left = newNode;

numberNodes++;

}

else

{

trailCurrent->right = newNode;

numberNodes++;

}

}

}

//Insert an item into the Binary Search Tree and "update" the given entry if certain qualifications take place

template

void BinarySearchTree::insert(const DataType &newItem, void(*duplicateItemFound)(DataType &existingItem, const DataType &newItem))

{

TreeNode *current; //pointer to traverse the tree

TreeNode *trailCurrent; //pointer behind current

TreeNode *newNode; //pointer to create the node

newNode = new TreeNode;

newNode->key = newItem;

newNode->left = nullptr;

newNode->right = nullptr;

if (root == nullptr)

{

root = newNode;

numberNodes++;

}

else

{

current = root;

while (current != nullptr)

{

trailCurrent = current;

if (current->key == newItem)//

{

duplicateItemFound(current->key, newItem);

return;

}

else if (current->key > newItem)

current = current->left;

else

current = current->right;

}//end while

if (trailCurrent->key > newItem)

{

trailCurrent->left = newNode;

numberNodes++;

}

else

{

trailCurrent->right = newNode;

numberNodes++;

}

}

}

template

void BinarySearchTree::update(DataType &exsitingItem, const DataType &newItem)

{

exsitingItem <= newItem;

}

//we will find the entries one by one and print them. That in theory is a traversal

template

void BinarySearchTree::traverse(void(*itemFound)(const DataType& foundItem)) const

{

inorder(root);

}

//This prints the tree starting from the given TreeNode

template

void BinarySearchTree::inorder(TreeNode *p) const

{

if (p != nullptr)

{

inorder(p->left);

std::cout << p->key;

inorder(p->right);

}

}

template

void BinarySearchTree::inorder2

(TreeNode *p) const

{

std::ofstream outputfile;

outputfile.open("pointerval.txt");

if (p != nullptr)

{

inorder2(p->left);

outputfile << "The memory location is: " << p << " " << std::endl;

inorder2(p->right);

}

outputfile.close();

}

#endif //PROJECT5EC_BINARYSEARCHTREE_H