CIS300 Spring 2005: Assignment 6 12 points; due Monday, 4 April, 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 implement a program that lets a user insert integer keys and strings into a database structured as a binary tree as shown above.

The GUI from Assignment 3 (package TestTheDatabase) has been slightly modified so that you can use it for this assignment. At www.cis.ksu.edu/~schmidt/300s05/Assign/Assn6/Assign6 is the new version of package TestTheDatabase, which builds the GUI. The demo version is structured like this:
where package TestTheDatabase holds the controller and frame classes and package DB holds class DummyDatabase (it does nothing) and interface Database (the connection point between the database and the GUI).

You must write class BinaryTreeDatabase implements Database, which replaces the DummyDatabase in the above diagram. The class you write will be inserted into package DB. BinaryTreeDatabase will maintain the binary tree of strings, like in the pictures seen above. BinaryTreeDatabase must have three public methods:

  1. insert(int key, String info), which uses key to insert info at the correct node in its binary tree.
  2. find(int key), which returns the info stored at position key (a positive integer).
  3. 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 GUI connects ``automatically'' to the class you write --- you merely change one line in class Start in package TestTheDatabase to make the connection.

What to do

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

class BinaryTreeDatabase uses a new data type, class BinarySpellingTree, that you define. The data type should have classes that construct

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.

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 www.cis.ksu.edu/~schmidt/300s05/Assign/Assn6/Assign6.

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 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.

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!

Submit the folder, Assign6, that holds package DB, package TestTheDatabase, package BitList, and any other packages you write or use. Compile all the files and test them. Execute javadoc on all the packages you write. Create Assign6.jar and submit at http://www.cis.ksu.edu/~schmidt/300s05/Assign/submit.html.