Java Reference
In-Depth Information
Nodes with the same parent are called
siblings;
thus
B, C, D,
and
E
are all
siblings. If there is a path from node
u
to node
v,
then
u
is an
ancestor
of
v
and
v
is a
descendant
of
u
. If
u
The
size of a node
is
the number of
descendants the
node has (including
the node itself).
v,
then
u
is a
proper ancestor
of
v
and
v
is a
proper descendant
of
u
. The
size of a node
is the number of descendants the
node has (including the node itself). Thus the size of
B
is 3, and the size of
C
is 1. The size of a tree is the size of the root. Thus the size of the tree shown in
Figure 18.1 is the size of its root
A,
or 11.
An alternative definition of the tree is recursive: Either a tree is empty or
it consists of a root and zero or more nonempty subtrees
T
1
,
T
2
, ...,
T
k
,
each
of whose roots are connected by an edge from the root, as illustrated in
Figure 18.2. In certain instances (most notably, the
binary trees
discussed
later in the chapter), we may allow some of the subtrees to be empty.
≠
18.1.2
implementation
One way to implement a tree would be to have in each node a link to each
child of the node in addition to its data. However, as the number of children
per node can vary greatly and is not known in advance, making the children
direct links in the data structure might not be feasible—there would be too
much wasted space. The solution—called the
first child/next sibling method
—
is simple: Keep the children of each node in a linked list of tree nodes, with
each node keeping two links, one to its leftmost child (if it is not a leaf) and
one to its right sibling (if it is not the rightmost sibling). This type of imple-
mentation is illustrated in Figure 18.3. Arrows that point downward are
firstChild
links, and arrows that point left to right are
nextSibling
links. We
did not draw
null
links because there are too many of them. In this tree, node
B
has both a link to a sibling (
C
) and a link to a leftmost child (
F
); some nodes
have only one of these links and some have neither. Given this representation,
implementing a tree class is straightforward.
General trees can
be implemented by
using the
first child/
next sibling method,
which requires two
links per item.
figure 18.2
A tree viewed
recursively
Root
• • •
T
1
T
2
T
3
T
k
Search WWH ::
Custom Search