Data Structures Assignment - Building a Binary Search Tree
In this assignment, you are to write a program that analyzes a selection of text, counting the number of times each word appears in the text. Your word counts must ignore capitalization, so the, The, THE, and tHe all increase the count for the word "the" by one. For purposes of this assignment, a word is any consecutive string of letters and the apostrophe character, so don't counts as a single word, and best-selling counts as two words: best and selling. Notice that a blank space will not necessarily occur between two words. Numbers such as 27 and 2/3 will NOT be counted as words.
You must store the words and the counts of the words in a single binary search tree. Each word occurring in the text can only be stored once in the tree. Call the structure for the nodes of the tree WordNode, and call the references in this structure left and right. Use Strings to store words in the tree. Call the class implementing the binary search tree WordTree. It must contain the following public methods:
- constructors
- add: adds the given word to the tree if it is not already in the tree OR increments the appropriate counter if it is already there. It returns nothing.
- countNodes: returns the number of words currently stored in the tree.
- countWordsWith4Chars: returns the number of words which have exactly four characters.
- print: display the words of the tree in alphabetical order, and next to each word, prints the number of times each word occurs in the text.
Three of these operations (all but add) must visit every node in the tree. One of these must use preorder traversal, one must use in order traversal, and one must use post order traversal. You must decide which to use for each method, but use comments to document the type of traversal used.
The WordTree class may have only one data member variable, root, and it must be private.
Your program should perform the following steps:
1. Prompt the user for the name of the file (a string). Use the string input by the user as an argument to open file:
2. Open the file on disk, and process its contents, adding unique words to the BST and increasing the counts of existing words if necessary
3. Repeat steps 1&2 until the user enters some sentinel value.
4. Print out the total number of nodes in your tree
5. Print out the number of words which have exactly four characters.
6. Print out the contents of a tree in alphabetical order.