Lab 7: Binary Trees
Due: Thursday, Mar. 24, 11:59pm
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 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.
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 encourage you to take a close look at the code and process for yourself what it is doing.
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:
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
For this part, you will write two utility methods for use with trees, and test them on a simple tree structure. Use the original myTree from the work above. In your main() method you will call the methods you write on myTree.
Now write two static methods in BinaryTree.java that will recursively traverse and print out the node values: inOrder() and postOrder(), which operate in the order described by their names. (Note that the printIndented() method supplied in BinaryTree.java is preorder, but it is far more complicated than what you need to write because it keeps track of the current level and prints an appropriate amount of indentation. Your methods can simply print the node values in the appropriate order, separated by spaces.) Call both of your functions on myTree to illustrate their behavior. Think about the return types for these two methods.
(Another note: it would be nice in principle to have traversal functions that could perform any operation on a tree node. This can be done by defining a TraversalFunction interface, and passing a class implementing the interface to the traversal method. However, you don't need to do that for this lab.)