CS102 Spring 2008

Lab # 8

ABST (Abstract Binary Search Tree) class hierarchy

In this laboratory exercise you will write a program that implements and a binary search tree, and tests its basic operations. This implementation differs from the one in the text. It follows a functional style, like the IList hierarchy (there will be no tests for a null reference).

Download starter project and launch NetBeans

1. Download the lab 8 starter project and unzip it in your cs102 directory.
2. Launch NetBeans and open the project named lab8.
3. The project includes many Java source files. You will be responsible for implementing the methods in : BSTLeaf.java, and BSTNode.java. Both of these classes implement the ABST abstract class, which is given.
4. The recursive definition of an ABST is as follows:
   An ABST is either:
• a BSTLeaf: containing no fields, i.e., an empty tree, or
• a BSTNode, containing fields: data, left, and right, where data is an Object, and left and right are ABSTs.
5. For each method, refer to the comments for how to proceed. 
6. Note: The ABST class hierarchy is similar in spirit to the IList hierarchy we've used earlier in the semester.
• The BSTLeaf class corresponds to the MTList class for the IList hierarcy; 
• the BSTNode class corresponds to the ConsList class for the IList hierarchy.
7. Save and run your project. Your output should look something like the following. When it does, submit your lab.  Here is the sample output:
   

init:
deps-jar:
compile:
run:
empty tree:
  Node()
BST containing a, b, and c nodes:
  Node(b, Node(a, Node(), Node()), Node(c, Node(), Node()))

testCountABST1: true
testCountABST2: true
testFindABST1: true
testFindABST2: true
testFindABST3: true
testRemoveABST1: true
testRemoveABST2: true
testRemoveABST3: true
BUILD SUCCESSFUL (total time: 0 seconds)

Submitting your work

For the remainder of the semester, submitting your work will be involve two parts: electronic and printouts.

First, the electronic. From a terminal window, type the following commands:

 cd
 cd cs102
        submit102 lab8

Second, print out your source code listing and hand in to your instructor. For this lab, print files BSTLeaf.java and BSTNode. If your instructor is not around, leave your printout in his mail bin, which is located outside the Computer Science Department office.

Log out

When you are done, close NetBeans, and then locate the logout button on the menu bar. Click on the logout button (red arrow pointing through an open door).  Choose "Logout..." and then click "Yes" when prompted.  Always remember to log out when you are done using the system, to ensure that no one else uses your account.