Trees - Data Structures and Abstractions with Java - page 577

We can define an interface for a basic binary tree by adding methods to those already in the
interfaces TreeInterface and TreeIteratorInterface . Since a Java interface can extend more
than one interface, we can write the interface shown in Listing 23-3 for a class of binary trees.

LISTING 23-3

An interface for a binary tree

package TreePackage;
public interface BinaryTreeInterface<T> extends TreeInterface<T>,
TreeIteratorInterface<T>

{

/** Sets this binary tree to a new one-node binary tree.
@param rootData

an object that is the data in the new tree's root

*/
public void setTree(T rootData);

/** Sets this binary tree to a new binary tree.
@param rootData an object that is the data in the new tree's root
@param leftTree the left subtree of the new tree
@param rightTree the right subtree of the new tree */
public void setTree(T rootData, BinaryTreeInterface<T> leftTree,
BinaryTreeInterface<T> rightTree);

} // end BinaryTreeInterface

The two setTree methods transform an existing binary tree object into a new tree composed of
given arguments. The first method forms a one-node tree from a given data object. The second
method forms a tree whose root node contains a given data object and has as its subtrees the two
given binary trees. A class that implements this interface certainly could have constructors that per-
form the same tasks as these two methods. However, since an interface cannot contain constructors,
we have no way to force an implementor to provide them.

23.19

Example. Suppose that the class BinaryTree implements the interface BinaryTreeInterface . To
construct the binary tree in Figure 23-13, we first represent each of its leaves as a one-node tree.
Notice that each node in this tree contains a one-letter string. Moving up the tree from its leaves, we
use setTree to form larger and larger subtrees until we have the desired tree. Here are some Java
statements that build the tree and then display some of its characteristics:

// represent each leaf as a one-node tree
BinaryTreeInterface<String> dTree = new BinaryTree<String>();
dTree.setTree("D");
BinaryTreeInterface<String> fTree = new BinaryTree<String>();
fTree.setTree("F");
BinaryTreeInterface<String> gTree = new BinaryTree<String>();
gTree.setTree("G");
BinaryTreeInterface<String> hTree = new BinaryTree<String>();
hTree.setTree("H");
BinaryTreeInterface<String> emptyTree = new BinaryTree<String>();
// form larger subtrees
BinaryTreeInterface<String> eTree = new BinaryTree<String>();
eTree.setTree("E", fTree, gTree); // subtree rooted at E