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

T he most common implementation of a tree uses a linked structure. Nodes, analogous to the nodes
we used in a linked chain, represent each element in the tree. Each node can reference its children,
which are other nodes in the tree. This chapter emphasizes binary trees, although it concludes with a
brief discussion of general trees. We do not cover binary search trees here, as the entire next chapter is
devoted to them.
Although we could use either an array or a vector to implement a tree, we will not do so in this
chapter. These implementations are attractive only when the tree is complete. In such cases, the link
between a parent and child is not stored explicitly, so the data structure is simpler than if the tree is
not complete. In Chapter 26, we will encounter a use for a complete tree, so we will postpone until
then any other implementation of the tree.

The Nodes in a Binary Tree

24.1

The elements in a tree are called nodes, as are the Java objects in a linked chain. We will use similar
objects to represent a tree's nodes and call them nodes as well. The distinction between a node in a
tree that you draw and the Java node that represents it usually is not essential.
A node object that represents a node in a tree references both data and the node's children. We
could define one class of nodes for all trees, regardless of how many children a node has. But such
a class would not be convenient or efficient for a node in a binary tree, since it has at most two chil-
dren. Figure 24-1 illustrates a node for a binary tree. It contains a reference to a data object and ref-
erences to its left child and right child, which are other nodes in the tree. Either reference to a child
could be null . If both of them are null , the node is a leaf node.

FIGURE 24-1

A node in a binary tree

Reference to another node, if any

Data object

Although the nodes in a linked chain belong to a private class Node that is internal to classes
such as LinkedStack and LList , our class of tree nodes will not be internal to the class of binary
trees. Since any class that extends our fundamental class of binary trees might need to manipulate
nodes, we will define our class of tree nodes outside of our binary tree class. But we will not make
this class of nodes public. Instead, we will give it package access within a package that contains the
classes of the various trees and their interfaces. In this way the node remains an implementation
detail that is not available to any of the tree's clients.

Note: A node object in a linked chain references another node in the chain. Although we
can process the chain recursively, a node does not reference a chain. Likewise, a node object
in a binary tree references other nodes in the tree. Although we often think of a binary tree
recursively, as Segment 23.8 describes, a tree node does not reference another tree.