CPSC 220 Fall 2007
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.
HW 8: Basic Binary Tree Code
To familiarize yourself with a basic binary tree implementation,
do the following:
- 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
- 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).
- 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()
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