Overview

You are to write a program that reads in a body of text and inserts the text into a binary tree class that you write from scratch based on alphabetical order. You should keep an instance count for each word in the text. Each time a duplicate word is added you should be able to update the instance count for that word.  At the end of the text insertion you will show statistics for the run.

Details

The purpose of this exercise is to give you familiarity with Binary Trees. You will read in a lengthy text file; Bram Stokers Dracula as text from guttenberg.org http://www.gutenberg.org/ebooks/345.txt.utf-8.   If you have problems search for 345 on Gutenberg.org, and select the Plain Text UTF-8 link.  As you read the text you will map all words to lower case, and remove all punctuation characters (Only numbers or letters should remain) removed characters should be eaten, NOT replaced with a space.  (Use the parser I will provide, it

does all this).  Once the words are pre-processed you will insert them into a binary tree.  Each item must be answered programmatically.

Do not modify the text file you download, although there are headers and footers from Gutenberg, please leave them intact.

When the binary tree is completely loaded you will perform queries to exhibit the following things:

•    How many times do the following words appear in the text?

o  transylvania                                                                      o  vampire

o  harker                                                                                o  expostulate

o  renfield                                                                              o  fang

•    What is the depth of the tree?

•    How many different words are there in the book?

•    What word is at the root of the tree?

•    Which word(s) are at the deepest leaves in the tree?

•    How many total words are in the book?

•    Which word occurs most frequently?

•    Display the first 20 words in a Pre-Order Traversal of the tree.

•    Display the first 20 words in a Post-Order Traversal of the tree.

•    Display the first 20 words in an In-Order Traversal of the tree.

No User Interface is required for this project.

Suggestions (Use at your discretion)

•    Download the text file to your local machine.

•    Write a program to test the parser before you start adding it to the tree

•    A dynamic tree is best suited for this

•    Include a counter in each tree record to handle duplicate words.

Grading

To receive full credit for this program the following must be submitted:

1) Pseudo code for the algorithms utilized.   (25%)

2) Well commented Syntactically Correct Java code.   (60%)

3) A run as instructed above.   (15%)