Java Reference
In-Depth Information
A
s a plant, a tree is well known. As a way to organize data, the tree is more familiar than you
might think. A family tree or a chart of players in a tournament are two common examples of a tree.
A tree provides a hierarchical organization in which data items have ancestors and descendants.
The organization is richer and more varied than any you have seen previously.
This chapter explores the ADT tree in its two forms—binary and general—and provides several
examples of how such trees are used.
23.1
The data organizations that you have seen so far have placed data in a linear order. Objects in a stack,
queue, list, or dictionary appear one after the other. As useful as these organizations are, you often must
categorize data into groups and subgroups. Such a classification is
hierarchical
,
or
nonlinear
, since
the data items appear at various levels within the organization.
We begin by looking at several familiar examples of hierarchical data. Each example will be
illustrated by a diagram that represents a tree.
Example: Family trees.
Your relatives can be arranged hierarchically in more than one way.
Figure 23-1 shows Carole's children and grandchildren. Her son Brett has one daughter, Susan.
Carole's daughter, Jennifer, has two children—Jared and Jamie.
Using a different arrangement, Figure 23-2 shows Jared's parents and grandparents. Jared's
father is John and his mother is Jennifer. John's father and mother are James and Mary; Jennifer's
parents are Robert and Carole.
FIGURE 23-1
Carole's children and grandchildren
Carole
Brett
Jennifer
Brian
Susan
Jared
Jamie
FIGURE 23-2
Jared's parents and grandparents
Jared
John
Jennifer
James
Mary
Carole
Robert
