Part 1Download BST.h and complete the file by defining the member functions.
Part 2Write a program that reads lines of text from a text file, extracts the words from the text and stores each word and an associated list of the lines numbers on which the word occurs. Your program should ask the user for the file name of the text file from which the words will be extracted, open the file and input a line at a time (use getline). Then output an alphabetical list of the words in the file and the line numbers on which each word occurs. Even if a word occurs more than once on a line only include the line number in the list once. The output should look like the following:
a
1 17 17 57 84 97 105 107 114 128 (assuming these are the 19 lines “a?? occurs on)
133 133 149 149 187 189 193 201 215
big
15 274
disrespectful
46
...
This program needs to repeatedly look-up a word to see if it is already stored and if so add the new line number to the associated list of line numbers. If the word is not stored then it needs to store it together with a new list which contains one line number. It also needs to output the words in alphabetical order together with their associated lists of line numbers. The ability to look-up keys (words) efficiently and output the keys in order is nicely provided by a binary search tree.
## Deliverables
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. (C++ in Unix)
2) Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables):
a) For web sites or other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment.
b) For all others including desktop software or software the buyer intends to distribute: A software installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request.
3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).
## Platform
C++ in Unix
This program can also serve to test how well balanced a binary search tree constructed from real test data is compared to the ideal of a perfectly balanced tree. A perfectly balanced binary tree with n nodes in it would have a height of floor(log2(n)). This could be computed in C as floor(log(n)/log(2)). These functions are in the math library so include <math.h> and compile the program using the link math library option, i.e. cxx -lm source_files when compiling on Bayou. Have operations SizeBST and HeightBST to compute the size (number of nodes) of the tree and the height of the tree. These functions should be defined recursively. Output the actual height of the tree and the height of a perfectly balanced tree with this number of nodes.