CIT 594 Assignment 2: A Binary Tree ADTSpring 2004, David Matuszek |

**Purposes:**

- To give you more practice with Eclipse and JUnit testing
- To reinforce the idea of ADTs (Abstract Data Types)
- To get you started with linked data structures
- To get you started using recursion

**General Idea:**

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.

**Details:**

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 `BinaryTree`

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*
for the `BinaryTree`

class.

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 `Object`

,
while the left and right children will be (references to) nodes.

Your assignment is to define the following classes and methods.

**class BinaryTree**

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.

Your `BinaryTree`

class should have the following fields:

**public Object value**- Note that this field is public. It doesn't matter to us what the user puts here, because nothing the user can do will affect the structure or validity of the binary tree.
**private BinaryTree leftChild**- This is a reference to another binary tree. It will be
`null`

if this BinaryTree node has no left child. **private BinaryTree rightChild**- This is a reference to another binary tree. It will be
`null`

if this BinaryTree node has no right child.

Your `BinaryTree`

class should have the following constructors:

public BinaryTree(Object value)

public BinaryTree(Object value, BinaryTree leftChild, BinaryTree rightChild)

Your `BinaryTree`

class should have the following methods:

**public BinaryTree getLeftChild()**- Returns the left child of this binary tree (which may be null).
**public BinaryTree getRightChild()**- Returns the right child of this binary tree (which may be null).
**public void setLeftChild(BinaryTree newLeftChild) throws IllegalArgumentException**- Replaces the current left child of this binary tree with the
`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`IllegalArgumentException`

. **public void setRightChild(BinaryTree newRightChild) throws IllegalArgumentException**- Replaces the current right child of this binary tree with the
`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`IllegalArgumentException`

. **public boolean isLeaf()**- Returns true if both children of this binary tree are
`null`

. This is a*convenience routine:*The user could do without it. **public boolean equals(Object object)**- Returns true if (1) the given object is a binary tree,
**and**(2) the value fields of the two trees are equal,**and**(3) the left subtrees are equal,**and**(4) the right subtrees are equal.(1) You have to be very careful of nulls; they have to be compared using

Notes:`==`

, 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 `value`

. They
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 `setLeftChild`

and `setRightChild`

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 `setLeftChild`

and `setRightChild`

methods will throw an exception when asked to construct an invalid binary tree.

**class ArithmeticExpression extends BinaryTree**

An `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
arithmetic expressions.

The `ArithmeticExpression`

class has the following constructors:

public ArithmeticExpression(Integer value)throws IllegalArgumentException - Creates an arithmetic expression with the given
`value`

and no children. The exception is thrown if the argument is`null`

.

public ArithmeticExpression(String value,ArithmeticExpression leftChild ,ArithmeticExpression rightChild )

throws IllegalArgumentException - Constructs an arithmetic expression with the given
`value`

and children. The exception is thrown if the value is not one of the strings`"+"`

,`"-"`

,`"*"`

, or`"/"`

, or if any argument is`null`

.

The class also has the following methods:

**public int evaluate()**- Computes and returns the value of the arithmetic expression. If the value
in the given node is
`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 `evaluate`

method, however.

This is *not* an industrial-strength class. It is awkward to build arithmetic
expressions, and the fact that the class inherits from `BinaryTree`

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 `ArithmeticExpression`

class.
Be thorough, and don't forget to test that exceptions are thrown when they should
be.

**public class AllTests**

This class will perform *all* JUnit tests. Eclipse will generate this
class for you.

**Due date:**

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**.