In this PROGRAM, you will be implementing a binary search tree. You must use a node-based implementation of a tree. Each node in the tree will be represented by a Node class and should have a left and right subtree pointer. Each node in your tree should hold a string (note: a string can hold more than one word) and also contain an integer count. Include the following functions for the tree. For each operation, I have included the function prototype that you must use so that your tree will interface with the main test file. This is by no means an exhaustive list of the functions that you will be writing. These functions must be public functions in your tree class.

Required Public Member Functions

-void insert(const string &): Insert an item into the binary search tree. Be sure to keep the binary search tree properties. When an item is first inserted into the tree the count should be set to 1. When adding a duplicate string (case sensitive), rather than adding another node, the count variable should just be incremented.

-bool search(const string &) const: Search for a string in the binary search tree. It should return true if the string is in the tree, and false otherwise.

-string largest( ) const: Find and return the largest value in the tree. Return an empty string if the tree is empty.

-string smallest( ) const: Find and return the smallest value in the tree. Return an empty string if the tree is empty.

-int height(const string &) const: Compute and return the height of a particular string in the tree. The height of a leaf node is 0 (count the number of edges on the longest path). Return -1 if the string does not exist.

-void remove(const string &): Remove a specified string from the tree. Be sure to maintain all binary search tree properties. If removing a node with a count greater than 1, just decrement the count, otherwise, if the count is simply 1, remove the node. You MUST follow the remove algorithm shown in the slides and discussed in class or else your program will not pass the test functions. When removing, if removing a leaf node, simply remove the leaf. Otherwise, if the node to remove has a left child, replace the node to remove with the largest string value that is smaller than the current string to remove (i.e. find the largest value in the left subtree of the node to remove). If the node has no left child, replace the node to remove with the smallest value larger than the current string to remove (i.e. find the smallest value in the right subtree of the node to remove).

Printing the tree

Print the tree in the following manners. When printing a node, print the string followed by the count in parentheses followed by a , and one space. You must follow these guidelines exactly. For example: goodbye(1), Hello World(3),

-void preOrder( ): Traverse and print the tree in preorder notation following the printing guidelines specified above.

-void inOrder( ):Traverse and print the tree in inorder notation following the printing guidelines specified above.

-void postOrder( ): Traverse and print the tree in postorder notation following the printing guidelines specified above.

Note about recursion

Some of the above functions used to interface with the main test file are not conducive for recursive methodology. However, you must write the inOrder, preOrder, postOrder, search, and remove functions recursively (you will lose points if you do not do these recursively). This may require you to overload 1 or more of the functions. For instance, preOrder is called from main but is not passed any parameter (you should not be able to pass the root from main because it should be a private variable of your tree class). However, you can overload the preOrder function so that it will operate recursively. For example, your preOrder function should look like this:

void Tree::preOrder( ) { preOrder(root); } 

and you will write the preOrder code within the recursive function that takes a node as a parameter. You may need to do something similar for the inOrder, postOrder, search, and/or remove functions so that you can write these functions recursively. Should these recursive helper functions be public or private?

Provided Files

***BSTree.h***

#ifndef __BSTREE_H__ #define __BSTREE_H__

#include "Node.h"

using namespace std;

class BSTree {

private: Node *root;

private: void preOrder(Node *) const;

public: void insert(const string &); bool search(const string &) const; void inOrder( ) const; void postOrder( ) const; void preOrder( ) const; string largest( ) const; string smallest( ) const; int height(const string &) const; void remove(const string &); };

#endif

****main.cpp****

#include #include "BSTree.h"

using namespace std;

void printOrders(BSTree *tree) { cout << "Preorder = "; tree->preOrder( ); cout << "Inorder = "; tree->inOrder( ); cout << "Postorder = "; tree->postOrder( ); }

int menu() { int choice = 0; cout << endl << "Enter menu choice: "; cout << endl; cout << "1. Insert" << endl << "2. Remove" << endl << "3. Print" << endl << "4. Search" << endl << "5. Smallest" << endl << "6. Largest" << endl << "7. Height" << endl << "8. Quit" << endl; cin >> choice; // fix buffer just in case non-numeric choice entered // also gets rid of newline character cin.clear(); cin.ignore(256, ' '); return choice; }

int main( ) {

BSTree tree;

int choice = menu();

string entry; while (choice != 8) { if (choice == 1) { cout << "Enter string to insert: "; getline(cin, entry); cout << endl; tree.insert(entry); } else if (choice == 2) { cout << "Enter string to remove: "; getline(cin, entry); cout << endl; tree.remove(entry); } else if (choice == 3) { printOrders(&tree); } else if (choice == 4) { cout << "Enter string to search for: "; getline(cin, entry); cout << endl; if (tree.search(entry)) { cout << "Found" << endl; } else { cout << "Not Found" << endl; }

} else if (choice == 5) { cout << "Smallest: " << tree.smallest() << endl; } else if (choice == 6) { cout << "Largest: " << tree.largest() << endl; } else if (choice == 7) { cout << "Enter string: "; getline(cin, entry); cout << endl; cout << "Height of subtree rooted at " << entry << ": " << tree.height(entry) << endl; } //fix buffer just in case non-numeric choice entered choice = menu(); } return 0; }

You will need to add other private helper functions to this BSTree class (constructor, deconstructor, and another else included) and you will need to make your own Node class.

Suggested Algorithms:

(1) Recursive implementation of inorder traversal

void inorder(Node* nodePtr)

if ( nodePtr ) {

inorder (nodePtr->left)

print node

inorder (nodePtr->right)

}

(2) -Make a stack of node pointers

-Operands - push a new tree onto the stack

-Operators - pop two trees from the stack. Use the operator as the root of a new tree with the popped trees as children. Push a new tree onto the stack

(3)Recursive implementation of search (private)

Node * search (Node *nodePtr, itemtype key)

if (!nodePtr){

return 0

}else if (nodePtr->item == key){

return nodePtr

}else if (nodePtr->item > key){

return search(nodePtr->left, key)

}else{

return search(nodePtr->right, key)

}

(4)Remove

? Five possible situations ?

-Item not found

-Removing a leaf

-Removing a node with one child - right only

-Removing a node with one child - left only

-Removing a node with two children

Deletion - Removing a node with children

-Otherwise the node has children - find replacement node

-If the left child exists

-----Replace node information with the largest value smaller than the value to remove

-----findMax(leftChild)

-Else there is a right child

------Replace node information with the smallest value larger than value to remove

------findMin(rightChild)

- Splice out replacement node (call remove recursively)

-Just copy in info of replacement node over the value to remove (overload = if necessary) ? Note - this is NOT the best solution if you have a large data structure. The overhead of the copy is too great and you should move the node instead.

-Delete replacement node if leaf