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.
Notes: (1) You have to be very careful of nulls; they have to be compared using ==, 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.