CPSC 220 Fall 2007
HW 8: Basic Binary Tree Code

A binary tree can be implemented as a linked structure, much like a linked list. The main difference is that a linked list is built out of LinearNode objects, each of which holds an element and a link to the next LinearNode; a binary tree, on the other hand, is built from BinaryTreeNode objects, each of which holds an element and links to the node's left and right children. A LinkedBinaryTree object, then, holds the root of the tree (a BinaryTreeNode) and perhaps some other information -- in the definition in the book, a count of how many nodes are in the tree.

To familiarize yourself with a basic binary tree implementation, do the following:

  1. Carefully read the section 12.4 (Implementing Binary Trees) in L&C. You don't have to examine every line of code, but be sure you understand the roles and structures of the BinaryTreeADT, LinkedBinaryTree, and BinaryTreeNode classes.

  2. Download the tree code in 12.4 to your directory and unzip it. It will create a directory called jss2 (stands for Java Software Structures 2nd edition, the name of the text). This directory is set up as a java package, so each class in the directory is in the jss2 package (you'll see that package jss2; is the first line in each file).

  3. The code for the LinkedBinaryTree class is not complete. Complete it by filling in code for the following methods: I strongly recommend that you write and test these one or two at a time. To do this you will need to put dummy return statements in some of the methods you haven't gotten to -- return null or 0, for example. Then you can use the test program below and comment out calls to the methods you have not yet implemented.

    You do not have to implement iteratorLevelOrder -- instead, have it throw an UnsupportedOperationException. So the body of the iteratorLevelOrder method will just be

    throw new UnsupportedOperationException()

  4. Download file TestBT.java into the directory that contains the jss2 directory (NOT into the jss2 directory itself). So if you have a hw8 directory, it should contain just two items: file TestBT.java and directory jss2. TestBT asks the user for a postfix expression and then builds and manipulates a simple expression tree. (Read the beginning of section 12.5 for an introduction to expression trees, but we are not using the ExpressionTree class in that section.) After building the tree, TestBT does the following:

    Use TestBT to test your tree code. You can comment out code you're not ready to test as suggested above, but otherwise do not modify the code in TestBT! If it doesn't work correctly, there's something wrong with your LinkedBinaryTree class -- that's what you should fix.