Tree Implementations - Data Structures and Abstractions with Java - page 617

General Trees

To wrap up our discussion of tree implementations, we will consider one way to represent a node
for a general tree. Rather than developing an implementation of a general tree that uses this node,
we will see that we can use a binary tree to represent a general tree.

A Node for a General Tree
24.19

Since a node in a binary tree can have only two children, it is reasonable for each node to contain
two references to these children. In addition, the number of node operations that test for, set, or get
each child is reasonable. But dealing with more children per node in this way quickly becomes
unwieldy.
We can define a node for a general tree that accommodates any number of children by refer-
encing an object, such as a list or a vector, that contains the children. For example, the node in
Figure 24-8 contains two references. One reference is to the data object, and the other is to a list of
child nodes. An iterator for the list enables us to access these children.

FIGURE 24-8

A node for a general tree

Data object

List of child nodes

In the interface for a general node given in Listing 24-6, getChildrenIterator returns an iter-
ator to the node's children. A separate operation adds a child to the node, assuming that the children
are in no particular order. If the order of the children is important, the iterator could provide an
operation to insert a new child at the current position within the iteration.

LISTING 24-7

An interface for a node in a general tree

package TreePackage;
import java.util.Iterator;
interface GeneralNodeInterface<T>
{

public T getData();
public void setData(T newData);
public boolean isLeaf();
public Iterator<T> getChildrenIterator();
public void addChild(GeneralNodeInterface<T> newChild);
} // end GeneralNodeInterface