CPSC 220 Fall 2002
Program 1: Iterators over Binary Trees
Write a binary tree class called BinaryTree with the following
interface:
- BinaryTree() -- creates an empty binary tree
- BinaryTree(Object item) -- creates a binary tree with
item
in the
root node and empty left and right subtrees.
- BinaryTree(Object item, BinaryTree left, BinaryTree right) -- creates a
binary tree with
item in the
root node and with left and
right as the left and right subtrees, respectively.
- Iterator iterator() -- returns an Iterator that performs an
inorder traversal of the tree's nodes.
- Iterator preorderIterator() -- returns an Iterator that performs an
preorder traversal of the tree's nodes.
- Iterator inorderIterator() -- returns an Iterator that performs an
inorder traversal of the tree's nodes.
- Iterator postorderIterator() -- returns an Iterator that performs a
postorder traversal of the tree's nodes.
Use a queue to construct each iterator, which means you will
also need to write a Queue class. Do not include an iterator in your
Queue class (or if you do, don't use it in your
BinaryTree class).
Testing your Iterators
File BTTest.class contains a program that
creates the following tree and uses its four iterators to print
preorder, inorder, and postorder traversals:
35
/ \
25 30
/ \
15 20
/ \
5 10
You may copy this file and use it initially to test your BinaryTree class.
(Be sure that you name your BinaryTree methods exactly as given above.)
However, when you think your BinaryTree class is correct, write your
own test class MyBTTest that constructs the tree below and uses its iterators
to print the traversals:
A
\
B
/ \
C D
/
E
/ \
F G
Documentation
Include the usual progam header (file name, your name, description of
program), plus a header for each method describing its parameters and
return value, if any, and its function. Also document any potantially
unclear portions of code.
What to Turn In
Turn in hard copy of your Queue.java, BinaryTree.java, and MyBTTest.java
classes.
Also tar your directory and e-mail it to bloss@roanoke.edu
(NOT bloss@cs.roanoke.edu). IMPORTANT: The subject should be
cpsc220 prog1.