Java Reference
In-Depth Information
will contain the classes that implement them. In this way, the package can contain implementation
details, such as a class of nodes, that we want to hide from the trees' clients. The next chapter will
examine these implementations.
23.16
Fundamental operations.
We begin with an interface that specifies operations common to all trees.
The interface in Listing 23-1 uses the generic type
T
as the type of data in the nodes of the tree.
LISTING 23-1
An interface of methods common to all trees
package
TreePackage;
public interface
TreeInterface<T>
{
public
T getRootData();
public
int
getHeight();
public
int
getNumberOfNodes();
public
boolean
isEmpty();
public
void
clear();
}
// end TreeInterface
This interface is quite basic. It does not include operations to add or remove nodes, as even the
specification of these operations depends on the kind of tree. We also did not include traversal oper-
ations in this interface, since not every application uses them. Instead we will provide a separate
interface for traversals.
23.17
Traversals.
One way to traverse a tree is to use an iterator that has the methods
hasNext
and
next
,
as given in the interface
java.util.Iterator
. As in previous chapters, we can define a method that
returns such an iterator. Since we can have several kinds of traversals, a tree class could have several
methods that each return a different kind of iterator. Listing 23-2 defines an interface for these meth-
ods. A tree class can implement this interface and define as many of the methods as are needed.
LISTING 23-2
An interface of traversal methods for a tree
package
TreePackage;
import
java.util.Iterator;
public interface
TreeIteratorInterface<T>
{
public
Iterator<T> getPreorderIterator();
public
Iterator<T> getPostorderIterator();
public
Iterator<T> getInorderIterator();
public
Iterator<T> getLevelOrderIterator();
}
// end TreeIteratorInterface
Many applications of trees in fact use binary trees. We could use a Java class of general trees for
such an application, but using a special class of binary trees is more convenient and efficient.
Because binary trees occur so frequently, developing special Java classes for them is worthwhile.
