CIS300 Fall 2004: Assignment 5

15 points; due Thursday, October 28, at 10:00pm

The structure of binary trees resembles the structure of binary numerals in a remarkable way: First, every binary numeral names a unique node in a binary tree,

where the quantity of digits in the numeral match the levels in the tree. More importantly, the digits give the path one takes from the root to reach the node:

where 0 means ``go left'' and 1 means ``go right.'' This suggests that we can use binary numerals as keys for storing objects in the nodes of a binary tree. The result is a special and important variant of spelling tree.

Your assignment is to implement a binary tree that saves strings whose keys are integers. The binary representation of the integer is used to store the string. For example, we might begin with an empty binary tree:

Say that we are asked to insert 3 "a", that is, insert the string "a" using its key, 3. Since 11 is the binary representation of 3, we store the string along the path labelled 1, 1:

(Note: the labels on the arcs are included merely for illustration.) A null fills a Node where there is no value. Next, say that we insert 12 "b". We get this tree:

because 12's binary representation is 1100.

Now, let's say that we try to find 3. Since 3 is 11 in binary notation, we move to the root (1) and then move to the right subtree (1). This gives us the node that holds "a", which is the answer. Similarly, find 12 must use 1100 as its path through the tree: start at the root (1), go right (1), go left (0), and go left again (0). This lands us at the node holding "b". Of course, an attempt to find 7 or find 4 returns no string.

Next, we might insert 7 "c". This gives us

Finally, say that we wish to print the contents of the tree in the command window:

3: a
7: c
12: b

(The usual in-order and pre-order printing algorithms do not print the strings in ascending-key order. To do this, you must use a queue --- see below.)

Programming assignment

You must construct a program, named StringBase, that constructs and maintains a binary tree of strings, like the one seen above. When StringBase.Start is started, the program accepts commands of these three forms:

insert NUM STR, which requests that a string, STR, is inserted using the positive integer, NUM, as its key. (If STR is successfully inserted, the program says so; if another string is already in the tree at position NUM, an error message is displayed.)
find NUM, which requests the string stored at position NUM (a positive integer). The program displays the string that is retrieved (or it displays an error message if no string is saved at position NUM).
print, which displays the complete contents of the tree in the command window. The contents are displayed in the format seen above in the ascending order of the keys.

The input commands can be submitted via input dialogs or text typed in the command window, but whatever you design, it should be obvious to the Grader how to submit the insert, find, and print commands.

What to do

If you would like some advice about how to solve this assignment in stages, please read the notes at http://www.cis.ksu.edu/~schmidt/300f04/Assign/Assn5/advice.html

Program structure

Your program should contain a ``controller'' class, Start, that asks the user for input commands and then executes the input commands one by one, constructing and printing the binary tree.

You must define a new data type, class BinarySpellingTree, which should have subclasses for

Leaves, which are empty, and also
Nodes which hold
1. a string value (or null, if no string is saved in the node) and the string's integer key (or -1, if no string is saved in the node)
2. (the links to) a left and a right subtree.

The binary tree you design can be mutable, that is, it can have setLeft and setRight methods. Or, you can work with an immutable tree.

In addition to class BinarySpellingTree, class Leaf, and class Node, you must also write some methods that (i) insert an integer-key-and-string into a tree, (ii) find a string in the tree, based on its key, and (iii) print the tree's contents.

So that you do not lose much time at programming the methods that convert integers into their binary codings, a helper package, package BitList, has been written for you to use. You can find it at http://www.cis.ksu.edu/~schmidt/300f04/Assign/Assn5.

The package contains the conversion methods, BitList.makeList(n) (this constructs and returns a binary numeral whose value is n) and BitList.intValue(b) (this calculates the integer value of the binary numeral, b). Within the coding of package BitList, you will find that binary numerals are modelled by Conslists (except here, they're called BitLists)--- the conslist coding will make it easy for you to read a binary numeral, one digit at a time, to find a path into your binary tree.

When your program processes a print command, the contents of your tree must be printed in proper numerical order. The usual in-order and pre-order traversal algorithms will not do this, because we must print the tree's contents ``one level at a time''; this is called breadth first printing.

A queue data structure can help us print the tree's contents properly. Here is an algorithm:

public void printBreadthFirst(BinarySpellingTree t) 
{ Queue q = new Queue();
  q.enqueue(t);   // start at the root
  while ( q is not empty )
      { BinarySpellingTree next = q.dequeue();
        if ( next is a Leaf )
        then there is nothing to print; forget about it!
        else  next  is a Node, so do the following:
             { print the key and value, if non-null, held within  next;
               q.enqueue(next.left());  q.enqueue(next.right());
             }
      }
}

The algorithm is adapted from the lecture notes on Queues. You can download package Queue from http://www.cis.ksu.edu/~schmidt/300f04/Lectures/QueueEx/

What to submit

You will get partial credit for a partial solution, so keep working even if you are unable to complete the entire assignment by the deadline!

Create a folder, Assign5, that holds package StringBase and any other packages you write or use (package BitList, package BinarySpellingTree, package Queue). Compile all the files and test them. Execute javadoc on all the packages you write. Create Assign5.jar and submit at http://www.cis.ksu.edu/~schmidt/300f04/Assign/submit.html.