Write a program that implements dynamic binary trees. The program will read in two text files one word at a time. (A “word?? will be any string of letters and numbers, including apostrophes. A word will end at a space, tab, quotation, or other punctuation mark. Ignore capitalization.)
The first text file “**[url removed, login to view]**?? will be a relatively long list of words, all spelled correctly. You should insert each of these into a binary tree. The order of the words will be randomized, so your tree should be fairly well balanced.
The second input file “**[url removed, login to view]**?? will be a free-form text file which may be taken from current news sources, or an English literature text, such as Mark Twain. For each word, check to see it that word (with that spelling) is contained in the dictionary tree. If it is not in the dictionary, put it into a separate tree of misspelled words. Continue reading words from the input file until you reach the end of file. .
Print out this initial list of misspelled words, and print out the count of words in this list.
Traverse your tree of misspelled words, and see if you can apply some simple rules to find a correctly spelled version in the dictionary. For example, if the misspelled word ends in **s** or **‘s** (apostrophe-s), try removing that letter or letters and see if it can be found in the tree. If it is found, remove it from the tree of misspelled words, and print it out as part of a list of “found words.?? This list should be in alphabetical order. Other simple things to try: Check for other suffixes such as a single apostrophe without an s, or **ed** suffix. (You are not expected to try _all possible_ suffixes, but as you look at the initial list of misspelled words, you will see some things to try. At a minimum, try the ones listed here.) At the end of this pass, print out the number of words found by each rule you used.
offer the user running your program the ability to add these words to the dictionary. (For simplicity , just go through the first 10 misspelled words.) If the user chooses to add them to the dictionary, then remove them from the misspelled word tree and add them to the dictionary tree.
Finally, print out the list of words still thought to be misspelled, and count them. Print out this final count.
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.