Solution to 96df: Tree nodes
See code at solutions/code/tutorialquestions/question96df
In my solution I define a TreeNode interface specifying the methods that all tree nodes should support:
I then define an abstract class, AbstractTreeNode, that implements this interface and specifies
data and behaviour that should be the same for all tree nodes:
public abstract class AbstractTreeNode<E> implements TreeNode<E> {
private E key;
@Override
public final E getKey() {
return key;
}
@Override
public final void setKey(E key) {
this.key = key;
}
}
Notice that here I have made the getKey and setKey methods final: Abstract``TreeNode
defines these methods once and for all.
I have not specified in this class how a node's children should be represented, nor have I provided implementations for
getNumberOfChildren, getChild or setChild, which are required by the TreeNode
interface. These methods are implicitly declared abstract in AbstractTreeNode.
Class BinaryTreeNode extends AbstractTreeNode to define the behaviour of a tree node that has
two children. The class declares two fields, one for each child:
private TreeNode<E> firstChild;
private TreeNode<E> secondChild;
In addition, the BinaryTreeNode class implements the getChild, setChild and getNumberOfChildren methods. The implementations
of these methods are straightforward. For example, getNumberOfChildren simply returns the integer 2.
LeafNode is a similarly simple class to represent nodes that have no children. Notice that the getChild
and setChild methods of this class use assert false to cause execution to abort if they are called.
Alternatively (and preferably) these methods could throw a runtime exception, e.g., an UnsupportedOperationException.
This would be preferable because a) assertion checking only happens if -ea is specified as a JVM argument, and b)
after throwing an exception there is no need for the method to return a value. This in getChild, we can simply write:
throw new UnsupportedOperationException();
instead of the less elegant:
assert false; return null;.
Nodes that are not binary or leaf nodes are represented by the class Arbitrary``TreeNode, which extends AbstractTreeNode
and provides the node representation and operations as shown in the original TreeNode class.
Extension: See the sample solution for an implementation of toString() in AbstractTreeNode.
This illustrates the power of abstract classes: we can write an algorithm to turn an arbitrary tree node into a string, even though the (direct and indirect)
children of the tree node may have different runtime types.