CSC 212: Programming with Data Structures

Lab 7: Binary Trees

Due: Thursday, Mar. 24, 11:59pm

Credit for this Lab: Nick Howe.

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 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.

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 encourage you to take a close look at the code and process for yourself what it 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 a BinaryTree<Double> variable called myTree in main.

  2. Build a tree with myTree 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 using the print() method. 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

Task Three

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.)

To Submit

  • BinaryTree.java (as modified by you)
  • TestBinaryTree.java
  • typescript showing your programs compile and run

Extra Credit Opportunity!

Write the method bsearch discussed in class on Tuesday, which should take in a query q, and an array a, and output the index of the value closest* to q. *If q is between two values, return the one with the lower index (which might not actually be closer, but is simpler). If you do this part, create a new file BinarySearch.java, with two (or more) methods: the main method testing your code, and a bsearch function. You could use the resulting array from the in-order traversal above as an test case, then try a variety of queries. Submit:
  • BinarySearch.java
Hint: use the Arrays.copyOfRange(array, startIdx, endIdx) method. In reality we don't need a copy, so there could exist a subarray method that is O(1), but this will do for now.