Please write in C++, thank you!

"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( ) const { 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

You can access a skeleton of the BSTree.h plus a very simple test harness (main.cpp) file in my Google drive

You will need to add other private helper functions to this BSTree class and you will need to make your own Node class."

Provided BSTree.h:

#ifndef __BSTREE_H__ #define __BSTREE_H__ class BSTree { private: Node *root; public: /* Constructors */ /* Default constructor */ BSTree(); ~BSTree(); /* Mutators */ /* Insert an item into the binary search tree. Be sure to keep BST 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 be incremented */ void insert(const string &newString); /* Remove a specified string from the tree. Be sure to maintain all bianry 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. */ void remove(const string &key); /* Accessors */ /* Search for a string in the binary search tree. It should return true if the string is in the tree, and false otherwise. */ bool search(const string &key) const; /* Find and return the largest value in the tree. Return an empty string if the tree is empty */ string largest() const; /* Find and return the smallest value in the tree. Return an emtpy string if the tree is empty */ string smallest() 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. */ int height(const string&) const; /* Printing */ /* For all printing orders, each node should be displayed as follows:  () e.g. goodbye(1), Hello World(3) */ void preOrder() const; void postOrder() const; void inOrder() const; }; #endif // __BSTREE_H__

Provided main.cpp:

#include  #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(numeric_limits::max(), ' '); return choice; } int main( ) { // Pass all your tests before running the executable main run_tests(); // TODO: Remove before submitting return 0; BSTree tree; int choice = menu(); string entry; while (choice != 8) { if (choice == 1) { cout << "Enter string to insert: "; } else if (choice == 2) { cout << "Enter string to remove: "; } else if (choice == 3) { } else if (choice == 4) { cout << "Enter string to search for: "; } else if (choice == 5) { cout << "Smallest: " << endl; } else if (choice == 6) { cout << "Largest: " << endl; } else if (choice == 7) { cout << "Enter string: "; } //fix buffer just in case non-numeric choice entered choice = menu(); } return 0; }