Java Reference
In-Depth Information
briefly outline the general techniques used to construct and manipulate trees. This sec-
tion is only a very brief introduction to trees to give you the flavor of the subject.
This section uses recursion, which is covered in Chapter 11.
Tree Properties
A tree is a data structure that is structured as shown in Display 15.39. In particu-
lar, in a tree you can reach any node from the top (root) node by some path that
follows the links. Note that there are no cycles in a tree. If you follow the links,
you eventually get to an “end.” A definition for a tree class for this sort of tree of
int
s is outlined in Display 15.39. Note that each node has two references to other
nodes (two links) coming from it. This sort of tree is called a
binary tree
, because
each node has exactly two link instance variables. There are other kinds of trees
with different numbers of link instance variables, but the binary tree is the most
common case.
The instance variable named
root
serves a purpose similar to that of the instance
variable
head
in a linked list (Display 15.3). The node whose reference is in the root
instance variable is called the
root node
. Any node in the tree can be reached from the
root node by following the links.
The term
tree
may seem like a misnomer. The root is at the top of the tree, and
the branching structure looks more like a root branching structure than a tree
branching structure. The secret to the terminology is to turn the picture (Display
15.39) upside down. The picture then does resemble the branching structure of a
tree, and the root node is where the tree's root would begin. The nodes at the
ends of the branches with both link instance variables set to
null
are known as
leaf nodes
, a terminology that may now make some sense. By analogy to an
empty linked list, an
empty tree
is denoted by setting the link variable
root
equal
to
null
.
Note that a tree has a recursive structure. Each tree has, in effect, two subtrees
whose root nodes are the nodes pointed to by the
leftLink
and
rightLink
of the root
node. These two subtrees are circled in Display 15.39. This natural recursive structure
makes trees particularly amenable to recursive algorithms. For example, consider the
task of searching the tree in such a way that you visit each node and do something
with the data in the node (such as writing it out to the screen). There is a general plan
of attack that goes as follows:
binary tree
root node
leaf node
empty tree
Preorder Processing
1. Process the data in the root node.
2. Process the left subtree.
3. Process the right subtree.
