Binary Search Trees & Histograms

1 Overview

Over the next few weeks well be doing a project in 2 weekly installments.

Week 1: create a binary search tree class

Week 2: use the binary search tree to create a word frequency histogram from a file it reads

in.

2 Problem

Write a program that uses a binary search tree to find out how many times each word in a writing sample occurs. Your program should do the following:

Read a text file. Build a binary search tree that uses data from the text file as it is read in:

If the next word isnt in the tree, add it to the tree

if the next word is in the tree, increment its count Print a word frequency histogram

3 Example

Input: This sentence repeats words because a sentence that repeats words makes a good example sentence.

Output:

a2 because 1 example 1 good 1 makes 1 repeats 2 sentence 3 that 1 this 1 words 2

4 Weekly Requirements

You may add additional data, constructors, and methods that you find helpful. You need to plan your own class and make your own decisions about the details of the data representation.

Week 1

Create a tree class.

Give your tree class the necessary private properties for a binary tree.

Create at least 1 constructor.

Create public methods to get/set all your private data fields.

Implement methods required for a binary search tree.

In your main method, thoroughly tests/demonstrate the methods from your tree that youve

implemented.

Week 2

Add code that will allow you to read in a file. I recommend using the scanner class. You can find the documentation here: http://docs.oracle.com/javase/1.5.0/docs/api/java/util/Scanner.html

For each word of your file, do one of the following: If that word already exists, increment a counter for that word by 1. If that word doesnt exist, insert it as a new node in the tree.

Print the word histogram.

Show the text file youll be reading in your screencast and submit it along with your code.