data structure 2

COSC 2007 –Data Structures II

Assignment #2

Due: Friday, February 14th, 2014

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 inorder traversal, and one must use postorder 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

Optional: if you have time, implement a method to delete every node from your BST that contains a word that is 3 or fewer letters long (note that you must explicitly make these deletions, not fail to insert these words in the first place).

Submission:

· Hand in your complete Java source code; and a copy of the resultsafter running your program ongiven file

· Upload your source code to CMS

· Demonstrate your program to TA before/on the due day

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.