http://www.gutenberg.org/ebooks/11

http://www.gutenberg.org/ebooks/2600

http://www.gutenberg.org/ebooks/2600

Please don't provide incomplete or incorrect answere. In such case, just skip it and go ahead. If you have any concerns, please mention it in the comments rather than putting it in your answer. You can download the txt files using the links. Thanks :)

1. Tree Functions For the first part of this lab, you will be implementing a binary search tree given the header file bst.h given above. You may have noticed by now that, unlike our previous BSTS, we are working with strings as keys in this lab. The tree nodes hold strings, and tree methods will have to interact with strings In addition to this, each BST node also has an int count, which is the frequency (or number of occurrences) of that word. In order to compare strings, you can use the regular comparison operators as the string class has overloads for these operators Here are the functions you will be required to implement BSTree) -BSTree0: Your typical BST constructor and destructor, BSTree() must initialize all of the tree's variables and BSTree) must delete all of the tree's nodes (you may use destroy(), as specified below) For the following four methods (search), insert(), remove), and treeHeight)) you should use the associated private helper function, which additionally takes a BSTNode as a parameter, to accomplish the algorithm recursively bool search(std:string); This function will search the BST for the given string, returning true if the string is found, and false otherwise void insert(std::string); This function will insert the word into the BST. If this word is already in the tree, the counter for the node will be incremented void remove(std::string); This function will search for the given string in the BST. If it finds the string, it will decrement the node's counter if it is greater than 1, or delete the node entirely (making any necessary changes to keep the tree a BST) unsigned int treeHeight0 This function will return the height of the tree void destroy (BSTNode*); This function will delete the entire tree in which the given BSTNode is the root This may be just a subtree, or the entire BST Once you have implemented and tested each of these methods, you may continue on to the rest of the lab 1. Tree Functions For the first part of this lab, you will be implementing a binary search tree given the header file bst.h given above. You may have noticed by now that, unlike our previous BSTS, we are working with strings as keys in this lab. The tree nodes hold strings, and tree methods will have to interact with strings In addition to this, each BST node also has an int count, which is the frequency (or number of occurrences) of that word. In order to compare strings, you can use the regular comparison operators as the string class has overloads for these operators Here are the functions you will be required to implement BSTree) -BSTree0: Your typical BST constructor and destructor, BSTree() must initialize all of the tree's variables and BSTree) must delete all of the tree's nodes (you may use destroy(), as specified below) For the following four methods (search), insert(), remove), and treeHeight)) you should use the associated private helper function, which additionally takes a BSTNode as a parameter, to accomplish the algorithm recursively bool search(std:string); This function will search the BST for the given string, returning true if the string is found, and false otherwise void insert(std::string); This function will insert the word into the BST. If this word is already in the tree, the counter for the node will be incremented void remove(std::string); This function will search for the given string in the BST. If it finds the string, it will decrement the node's counter if it is greater than 1, or delete the node entirely (making any necessary changes to keep the tree a BST) unsigned int treeHeight0 This function will return the height of the tree void destroy (BSTNode*); This function will delete the entire tree in which the given BSTNode is the root This may be just a subtree, or the entire BST Once you have implemented and tested each of these methods, you may continue on to the rest of the lab