Worksheet 3

This workshop is about Binary Search Trees.

Part 1

Look at the online documentation for the SearchTree class to remind yourself of the methods provided for binary search trees.

Now copy the SearchTreeDemo.java demo program to your area and run it. Try to understand what each line is doing.

Part 2

Now change the line

    t = t.add(new Integer(item));

in your copy of SearchTreeDemo.java to just

    t.add(new Integer(item));

Recompile the code and run it. Try to understand (a) why the code still compiles but (b) why it does something different.

You could also try doing the same thing with the

    t = t.remove(new Integer(item));

line towards the end.

Part 3

Now copy the file MySearchTreeDemo.java to your area and compile and run it. This is a different demonstration program. By examining the code, draw a diagram of the tree that it constructs. To check that you have got it right

(a)

add the line of code

    System.out.println("tree = " + t);

to print the tree as a string;

(b)

print out the elements of the tree in level order by replacing the t.elementsInOrder enumeration by the t.elementsLevelOrder enumeration.

Now reverse the sequence in which words are added to the tree, so that the insertion begins with "snow" and ends with "mary". What does the tree now look like? What are its inOrder and levelOrder enumerations?

Part 4

To do this part you need to modify the source code for the SearchTree class and its extensions. Take a copy of the file SearchTree.java and place this in your working directory. Note that this is slightly different from the DataStructures package version, but only in that the line

package DataStructures;

at the top has been replaced by

import DataStructures.Queue;
import DataStructures.QueueArray;
import DataStructures.Stack;
import DataStructures.StackArray;

so that this file can stand alone. You should now remove the line

import DataStructures.*;

from the top of your MySearchTreeDemo.java file, so that the compiler now picks up your local copy of SearchTree.java.

Now work on your copy of the source file SearchTree.java as follows. Introduce a method

    public abstract int nrLevels();

into the abstract SearchTree class. This method should count the total number of levels in the tree (the length of the longest path from the root to some leaf). Now implement this method in both the EmptyTree and NodeTree subclasses. (Hint: this is very similar to the nrNodes method. It is only one line in each case. For a NodeTree, think about how the number of levels in the tree depends on the number of levels in its left and right sub-trees. You may find the Math.max method useful.)

Add some code to your MySearchTreeDemo.java file to exercise the nrLevels method, and check that the results agree with your description of the original tree (and the one obtained by inserting in the opposite order).