CPSC 220 Fall 2007
HW 8: Basic Binary Tree Code

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:
   • removeRightSubtree
   • removeAllElements
   • isEmpty
   • size
   • contains
   • toString
   • iteratorPreOrder
   • iteratorPostOrder
   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:
   • uses a postorder traversal to print the expression in postfix
   • uses a preorder traversal to print the expression in prefix
   • uses an inorder traversal to print the expression in infix (without parentheses)
   • prints the number of nodes in the tree
   • prints whether the tree contains the character 2
   • prints a string representation of the tree
   • prints whether the tree is empty
   • removes all elements from the tree
   • again prints whether the tree is empty

   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.