Course Links

Exercises

Resources

External

Overview

The purpose of this lab is to familiarize you with binary trees and some of the code we will use to create and manipulate them. You will have several tasks to complete, beginning with some simple coding and moving to more complex tasks.

You will be working with a partially completed file as a base: BinaryTree.java. It has been filled in with comments; all you need to do is complete the code. During the lab you will write TestBinaryTree.java to test the class definition. You will also write TreePractice.java, as described below.

Task One

For the first part of this lab, you will complete the code in BinaryTree.java. Start with the accessors and manipulators. The return types and argument types have been deleted. Think about what they should be, and replace them.

Next, look at the other methods. At various points in the program (isLeaf, isBranch, and printIndented, references to the right child have been deleted. Your job is to find these points and add the appropriate code back in. (Hint: nearly always, you will do the same thing with the right child as you do with the left.) The purpose of this exercise is not so much to make you figure out on your own how to implement binary trees, but to force you to take a close look at the code and process for yourself what it is doing. At each point where you insert code, you should also place a short comment indicating what the inserted code is doing.

Task Two

For this part of the lab, you will write a test file called TestBinaryTree.java that will test the class definitions we've been creating. This should do the following:

  1. Create four BinaryTree<Double> variables called t1, t2, t3, and t4.
  2. Build a tree with t1 as the root, using the available methods to set children (e.g., t1.setLeft(new BinaryTree<Double>(3.5)), for example). Your tree should be structured as follows: 4.0 at the root; 3.5 and 5.5 as its left and right children; 1.25 and 3.75 as the children of 3.5; 4.75 and 8.5 as the children of 5.5; 7.0 and 13.0 as the children of 8.5. Print out this tree. The result should look like this: 
    Root:  4.0
  Left:  3.5
    Left:  1.25
    Right:  3.75
  Right:  5.5
    Left:  4.75
    Right:  8.5
      Left:  7.0
      Right:  13.0
  3. Create a deep copy of t1 in the variable t2. Verify that the deep copy was successful by changing the root of t2 to -1 and printing both trees. They should now differ, since only t2 was changed.
  4. Create a reference copy of t1 in the variable t3. Verify that it is not a deep copy by changing the right child of t3 to 6.25 and printing the original tree, t1. It should show the same change.
  5. Create a new tree with t4 as the root, that has t1 as its left subtree and t2 as its right subtree. The data value at the root of the new tree should be 0. Print out the new tree. Note that the tree t1 has not changed, even though it is now a subtree of a larger structure. Print out tree t1 again just to verify this. Then change an element in t1 and print out t4 to verify that the change is visible there too. Here we have a case similar to shallow copying, only it is just part of a larger structure in memory that is shared. Usually such situations should be avoided or approached with care; here we are interested in it for illustrative purposes only.

Task Three

For this part, you will write several utility methods for use with trees, and test them on a simple tree structure. Use the original t1 from the work above. Start a new file called TreePractice.java. Your main() method in this file will create t1 and call the various other methods on it.

Begin with a method we will call preToString, shown below.

    /** Simple recursive routine to convert a tree to a string*/
    public static String preToString(BinaryTree tree) {
    	String result = "-";
	if (tree != null) {
	    result = tree.getData().toString()+" "+preToString(tree.getLeft())+" "+preToString(tree.getRight());
	}  
        return result;
    }

Now write two versions (inToString and postToString) where you move the position of the getData portion relative to the recursive calls (between them in one, and after them in the other). Test them out on one of your trees, making sure to print a blank line in between so you can tell the calls apart. Study and compare the behavior of the three methods. How do they differ? If you know about tree traversal order, can you connect each method to a particular type of traversal?

To Submit