CS 223 In-lab 7
Week of 3/20

For CS 223, in-labs will consist of a mix of exercises and problems and short programming assignments.  These will be due at the end of the lab period.  You may occasionally be assigned homework problems as well.  Homework will always be due at the beginning of the next lab.

Saving Binary Trees to a File

For this in-lab, your goal is to write code that will save a binary search tree to a file.  Starting the BinarySearchTree classes that we developed in class, you should add two methods to the BinarySearchTree class:

public void saveToFile(String FileName) - this should save the binary search tree to a file.

In order to do this, first assign an index number (starting with 0 for the root) to each node in the tree (easiest to just add an integer index to the SearchNode class). Then do another traversal of the tree and create a file that looks like this:

<number of tree nodes>
<index of first internal node> I <index of left child> <index of right child>  <key value>
<index of second internal node> I <index of left child> <index of right child> <key value>
...
<index of first leaf node> L <key value>
...

Example:
5
0 I 1 2 20
1 L 10
2 I 3 4 30
3 L 25
4 L 40

represents the search tree:

        +---40
    +---30
    |   +---25
+---20
    +---10

and finally create new constructor:

public BinarySeachTree(String fileName)

This should read the text file specified by fileName and construct a new binary search tree as described in the file.  Create an empty tree if the file doesn't exist.

Modify the driver in order to save and read some test files.  Show that you can successfully build a search tree, print it out, save it to a file, read back in, and print it out again.  The trees should be identical.

What to Turn In

• Source code and three sample runs (the above and two of your own creation).