CPSC 220 Fall 2003
Program 2: A Binary Tree Class
Write a binary tree interface called BinaryTreeADT with the following
methods:
- boolean isEmpty() -- returns true if the tree is empty.
- int size() -- returns the number of nodes in the tree.
- boolean contains(Object target) -- returns true if the target is
in the tree (using equals to compare), false otherwise.
- Object find(Object target) -- returns the found element
if the target is in the tree (using equals to compare),
null otherwise.
- void removeLeftSubtree() -- removes the left subtree from the tree.
- void removeRightSubtree() -- removes the right subtree from the tree.
- void removeAllElements() -- makes the tree empty.
- Iterator iteratorPreOrder() -- returns an Iterator that performs a
preorder traversal of the tree's nodes.
- Iterator iteratorInOrder() -- returns an Iterator that performs an
inorder traversal of the tree's nodes.
- Iterator iteratorPostOrder() -- returns an Iterator that performs a
postorder traversal of the tree's nodes.
- Iterator iteratorLevelOrder() -- returns an Iterator that performs a
postorder traversal of the tree's nodes.
Then write a class BinaryTree that implements the BinaryTreeADT.
Be sure to include the three constructors we discussed in class:
- 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.
In the BinaryTree class, use a queue to construct the iterators; you may use the
LinkedQueue class
if you wish, which implements the QueueADT class
in the text. (To use the Linked Queue class you'll need the
LinearNode and
LinkedIterator classes as well.)
Note that the QueueADT has an iterator() method, so once
you get all the elements on the queue in the correct order, you can just
return the queue's iterator.
You'll need to write a BTNode class as well to support the linked
implementation.
Testing your BinaryTree class
File BTTest.class contains a program that
creates the following tree,
and uses its four iterators to print
preorder, inorder, postorder and levelorder traversals:
35
/ \
25 30
/ \
15 20
/ \
5 10
It also lets the user search for various values in the tree, prints the
total number of nodes in the tree, and performs some remove operations.
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 potentially
unclear portions of code.
What to Turn In
Turn in hard copy of your BinaryTreeADT.java, BinaryTree.java, BTNode.java, and MyBTTest.java classes.
Also tar your directory and e-mail it to bloss@roanoke.edu
with cpsc220 prog2 in the subject.