Java Reference
In-Depth Information
A
B
C
D
E
F
G
I
H
J
Figure 8-1.
A tree
The root is
A
. There are three subtrees rooted at
B
,
C
, and
D
, respectively. The tree rooted at
B
has two subtrees, the
one rooted at
C
has no subtrees, and the one rooted at
D
has one subtree. Each node of a tree is the root of a subtree.
The
degree
of a node is the number of subtrees of the node. Think of it as the number of lines leaving the node.
For example, degree(
A
) = 3, degree(
C
) = 0, degree(
D
) = 1, and degree(
G
) = 3.
We use the terms
parent
,
child
, and
sibling
to refer to the nodes of a tree. For example, the parent
A
has three
children, which are
B
,
C
, and
D
; the parent
B
has two children, which are
E
and
F
; and the parent
D
has one child,
G
,
which has three children:
H
,
I
, and
J
. Note that a node may be the child of one node but the parent of another.
Sibling nodes are child nodes of the same parent. For example,
B
,
C
, and
D
are siblings;
E
and
F
are siblings;
and
H
,
I
, and
J
are siblings.
In a tree, a node may have several children but, except for the root, only one parent. The root has no parent. Put
another way, a nonroot node has exactly one line leading
into
it.
A
terminal
node (also called a
leaf
) is a node of degree 0. A
branch
node is a nonterminal node.
In Figure
8-1
,
C
,
E
,
F
,
H
,
I
, and
J
are leaves, while
A
,
B
,
D
, and
G
are branch nodes.
The
moment
of a tree is the number of nodes in the tree. The tree in Figure
8-1
has moment 10.
The
weight
of a tree is the number of leaves in the tree. The tree in Figure
8-1
has weight 6.
The
level
(or
depth
) of a node is the number of branches that must be traversed on the path to the node from the
root. The root has level 0.
In the tree in Figure
8-1
,
B
,
C
, and
D
are at level 1;
E
,
F
, and
G
are at level 2; and
H
,
I
, and
J
are at level 3. The level of
a node is a measure of the depth of the node in the tree.
The
height
of a tree is the number of levels in the tree. The tree in Figure
8-1
has height 4. Note that the height of a
tree is one more than its highest level.
If the relative order of the subtrees T
1
, T
2
, …, T
m
is important, the tree is an
ordered
tree. If order is unimportant,
the tree is
oriented
.
A
forest
is a set of zero or more disjoint trees, as shown in Figure
8-2
.
A
D
G
B
C
H
I
J
E
F
Figure 8-2.
A forest of three disjoint trees
While general trees are of some interest, by far the most important kind of tree is a binary tree.
Search WWH ::
Custom Search