|CIT 594 Assignment 2: A Binary Tree ADT
Spring 2004, David Matuszek
Implement binary trees, and use binary trees to represent and evaluate arithmetic expressions. Use Eclipse. Provide good Javadoc documentation for all public fields, constructors, and methods.
An abstract data type has a contract with its users, which is specified
by its public members and described via Javadoc. It provides certain operations,
and restricts access to only those operations. Your
class is such an ADT.
In addition, any class is responsible for ensuring the validity of its data.
In this assignment, you are to take that responsibility very, very seriously
A binary tree is composed of nodes. Each node has a value, a left child, and
a right child. For maximum generality, the value will be of type
while the left and right children will be (references to) nodes.
Your assignment is to define the following classes and methods.
This is your ADT class. Each object in the
BinaryTree class represents
a single node; however, nodes are linked together, so that any node may be considered
as the "root" of a complete binary tree.
BinaryTree class should have the following fields:
public Object value
private BinaryTree leftChild
nullif this BinaryTree node has no left child.
private BinaryTree rightChild
nullif this BinaryTree node has no right child.
BinaryTree class should have the following constructors:
public BinaryTree(Object value)
public BinaryTree(Object value, BinaryTree leftChild, BinaryTree rightChild)
BinaryTree class should have the following methods:
public BinaryTree getLeftChild()
public BinaryTree getRightChild()
public void setLeftChild(BinaryTree newLeftChild) throws IllegalArgumentException
newLeftChild, provided that the resultant binary tree is valid (see below). If the operation would result in an invalid binary tree, the binary tree is unchanged and the method throws an
public void setRightChild(BinaryTree newRightChild) throws IllegalArgumentException
newRightChild, provided that the resultant binary tree is valid (see below). If the operation would result in an invalid binary tree, the binary tree is unchanged and the method throws an
public boolean isLeaf()
null. This is a convenience routine: The user could do without it.
public boolean equals(Object object)
==, while non-null objects must be compared using
equals(Object), and (2) this method is recursive. Also note that you will need this method in order to do unit testing on your BinaryTree class.
Note that there are no getter or setter methods for
are unnecessary because this is a public field and we don't care how it is used.
A binary tree will be considered valid if there are no loops in it.
If, starting from some node in the tree and following child links you can get
back to the same node, then there is a loop and the tree is invalid.
You need to test for validity in the
methods. We will, however, allow subtrees to be shared, provided there
are no loops.
I propose the following algorithm. If
n is the node to which the
new child is to be added, search the new child (which is itself a binary
tree) to see if node
n already occurs in it. If it does not, we
can go ahead with the operation. Note that (1) we are searching for the identical
==) node, not an equal one, and (2) the search is inherently recursive.
Is this algorithm sufficient to guarantee validity (no loops)? You should think
about this, but in any case this is the algorithm you should use. You will need
a (recursive) private search method to implement the test. Since the search
method will be private, you do not need to test it explicitly--rather, you test
it implicitly, by making sure that your
methods will throw an exception when asked to construct an invalid binary tree.
class ArithmeticExpression extends BinaryTree
ArithmeticExpression class could be an ADT, but in this assignment
it will just be a user of the
BinaryTree class, and imperfectly
implemented. You should do full JUnit testing and Javadoc documentation, but
you don't need to be overly concerned about the possibility of creating invalid
ArithmeticExpression class has the following constructors:
public ArithmeticExpression(Integer value)
- Creates an arithmetic expression with the given
valueand no children. The exception is thrown if the argument is
public ArithmeticExpression(String value,
, ArithmeticExpression leftChild ) ArithmeticExpression rightChild
- Constructs an arithmetic expression with the given
valueand children. The exception is thrown if the value is not one of the strings
"/", or if any argument is
The class also has the following methods:
public int evaluate()
Integer, it is just unwrapped and returned. If the value in the given node represents an arithmetic operation, the two children are (recursively) evaluated, the operation is performed (leftChild op rightChild), and the result is returned.
This class inherits several methods from
BinaryTree, which you
do not need to unit test. If the methods worked for other binary trees,
they will work for this one. You do need to unit test your
This is not an industrial-strength class. It is awkward to build arithmetic
expressions, and the fact that the class inherits from
means that it is very easy to use inherited methods to build invalid arithmetic
expressions. Don't worry about making this class bulletproof, and test your
evaluate method only with valid arithmetic expressions.
public class BinaryTreeTest
This is a JUnit test class for the
BinaryTree class. Be thorough,
and don't forget to test that exceptions are thrown when they should be.
public class ArithmeticExpressionTest
This is a JUnit test class for the
Be thorough, and don't forget to test that exceptions are thrown when they should
public class AllTests
This class will perform all JUnit tests. Eclipse will generate this class for you.
Please turn in your completed program, including all Java source and class files and all Javadoc generated documentation, via Blackboard, before midnight Thursday, January 29.