These lab exercises describe the work you will do with binary trees. All the useful and potentially reuseable stuff you build for binary trees will be stored in a single Java package named btree. Your application program will import classes from this package in the same way you are accustomed to importing Java API classes.

Navigate to the directory you are going to be using as your "home directory" for this lab exercise and create a new folder named btree in that directory. The basic binary tree tools you create will be stored in this Java package. Save the files BNode.java, BTree.java and BSTree.java in this directory. You will be implementing some methods in the BSTree class for these labs.

Notice the use of "generic types" in the BNode class. It's a simple class, but you should study its carefully to figure out how it works. It's purpose is to describe a node in a binary tree. Each object of type BNode will contain two fields of type BNode, which are pointers to two "children". Each node will also carry a piece of data. Instead of just declaring the data to be of type Object, Java allows a "type parameter" to be supplied as part of the definition. The actual value for this parameter is instantiated by the application program that uses this class. The letter T (enclosed in angle brackets) in the BNode definition represents the type for the data that will be stored in the node.

The BTree class definition is a generic description of a binary tree. BNodes can be the building blocks for any type of binary tree. Because there are lots of different ways to build binary trees, it isn't possible, in general, to know how to implement every method our binary trees might have. There are some (like isEmpty(), for example) that are simple to implement. The implementation of other methods might have to wait until we know precisely what sort of binary tree we are going to build. For this reason, the BTree class is defined as an "abstract class" where we implement the methods we know how to implement and identify the others as "abstract" methods.

Study the code in the BTree class to familiarize yourself with its use of generic types and abstract methods. Notice that the insert and delete methods in the BTree class are declared as abstract methods and the class is declared to be an abstract class (because it contains one or more abstract methods). The abstract BTree class has a constructor which initializes its fields, but this constructor cannot be invoked directly by an application program as there is no way to build an instance of this class (because of the missing method definitions). This abstract class must be extended by another class definition which implements the insert and delete methods. That extending class could also override some the the methods definitions that are defined in the BTree class.

When you examine the code in the BTree class, you will see that public methods named isEmpty(), preorder(), preorder_display() and find() have been coded. There is also a private preorder() method that has been coded. There is some work left for you to do to complete the coding of this abstract class. Part of that work is to code inorder() and postorder() methods which can be similar to the preorder() method provided. These preorder(), inorder() and postorder() methods will traverse the nodes of the tree in slightly different ways. Your textbook also contains the code for these traversal methods and its accompanying applets will demonstrate how they work.

Another feature of this abstract BTree class is the recommendation that the find() method, which is defined but may be inefficient for certain types of trees, should be overridden. Some type of binary trees will support faster search methods than the sequential algorithm used by this "default" find() method.

Your job for these labs is to implement the insert(), delete() and find() methods for the BSTree class as well as to implement the missing traversal methods for the BTree class. To keep things simpler, you should do these things one at a time.

Lab 7: Code the inorder and postorder traversal methods for the BTree class. You can pattern them after the preorder methods which have been provided. Add statements to the testBTree program, or write an entirely new test program is you wish, to test your new methods and make sure that they work correctly.

Lab 8: Code the insert() method for the BSTree class. Then, code an efficient find() method for this class which overrides the default find() method in the BTree class. Implement both of these operations recursively. Test them to make sure they work correctly.

Lab 9: Code the delete() method for the BSTree class. Do it recursively. Test to make sure it works correctly in all cases (deleting a leaf, deleting a node with one child, deleting a node with 2 children).

Make sure that you can actually compile and run the code in your "package". For this purpose, create a new source code file named testBTree.java in your home directory. DO NOT PUT THIS FILE IN YOUR PACKAGE FOLDER ... PUT IT IN THE PARENT DIRECTORY OF THAT FOLDER. The contents for this application program, intended for use in testing your implementations, are displayed below.

import btree.*;
import java.io.*;

public class testBTree {
	public static void main(String []args) {
		
		System.out.println("Creating a non-empty demo tree");
		BSTree<Integer> demo = new BSTree<Integer>(-1);
		System.out.println("PreOrder Traversal of the demo tree");
		demo.preorder_display();
		System.out.println("Traversal completed");
				
		System.out.println("Creating an empty tree");
		BSTree<Integer> t = new BSTree<Integer>();
		System.out.println("Created an empty tree");
		System.out.println("PreOrder Traversal of the empty tree");
		t.preorder_display();
		System.out.println("Traversal completed");
				
		System.out.println("Creating and traversing a forest of 40 empty trees");
		BSTree[] forest= new BSTree[40];
		for (int i=0; i< forest.length; i++) {
			forest[i] = new BSTree<Integer>();
			forest[i].preorder_display();
		}
		
		System.out.println("exiting");
	}
}