Lab
7: Building a Dictionary (and working with Binary Search Trees)
Official Due Date: Wednesday December 10th, 23:59.
(Note: You may submit this lab with no penalty till 12/12/01)
Background
Lab 7 will provide you an opportunity to get some practice
with a recursive data structure, the binary search tree (BST). This is
the last major data structure that 15-111 will explore. You need not code
the dictionary as a class (although you can if you desire). For this lab,
we want you to gain experience with the BST data structure as well as additional
practice with recursive data structures and routines.
What You'll Need
Download the lab7.zip file from the 15-111 course web site.
You should see the following files:
-
driver.java
-
FileInput.java
-
tree.java
-
project.mcp
-
bigdata.txt - a file of 172,822 words, one per line
-
smalldata.txt - a file of 15 words, one per line
Assignment
You will implement a dictionary of over 170,000 words as
a binary search tree. Your program must implement the following functionality:
-
Read a file of words (one word per line) and insert each
word into a binary search tree ordered on the word's value (ascending order
- smallest string must be in the left-most node)
-
Determine and print a frequency count of the depths of the
leaves
-
Allow the user to perform the following operations:
-
[f]ind - prompts the user for a word and informs the
user if the word is in the dictionary
-
[a]dd - prompts the user for a word and adds it to
the dictionary if it is not already there. If the word is already in the
dictionary, the word should not be added (again) and the user should be
informed it was already in the dictionary.
-
[d]elete - prompts the user for a word and deletes
it from the dictionary if it is there. If it is not there, the user should
be informed that the word wasn't found.
-
[p]rint - prints the dictionary in alphabetical order
-
[q]uit - terminates execution of the program
The smalldata.txt file will form a complete balanced
tree of 15 nodes. The [p]rint option is to assist you in debugging your
code on the small data file. It is suggested that you save the [d]elete
routine until last! Recall from lecture that the easiest case to delete
is a leaf node. Once you are sure you can delete a leaf, proceed to the
one-child case and, ultimately, to the two-child case. Do NOT try to implement
the entire delete routine all at once.
Sample Output
Building Tree:
bigdata.txt or smalldata.txt ==> smalldata.txt
Just built tree with 15 nodes
Determining leaf depth frequency on 8 leaves:
depth count
3 8
User Interface for Lab 7:
************************************
Find a word ==> [f]
Add a word ==> [a]
Delete a word ==> [d]
Quit program ==> [q]
input: q
--------------------------------------------------------------------------------
Building Tree:
bigdata.txt or smalldata.txt ==> bigdata.txt
Just built tree with 172822 nodes
Determining leaf depth frequency on 57647 leaves:
depth count
7 1
8 9
9 17
10 45
11 122
12 252
13 500
14 895
15 1346
16 2046
17 2969
18 3813
19 4658
20 5141
21 5540
22 5523
23 5302
24 4736
25 3901
26 3041
27 2481
28 1781
29 1335
30 899
31 533
32 328
33 208
34 121
35 58
36 20
37 12
38 5
39 7
40 2
User Interface for Lab 7:
*************************************
Find a word ==> [f]
Add a word ==> [a]
Delete a word ==> [d]
Quit program ==> [q]
input: q
Handing in your Solution
Your solution should be in the form of a .zip file and should
contain all files (except bigdata.txt)
Use the Intro Programming
dropoff
form to submit your zip file.