Trees - Data Structures and Problem Solving Using Java - page 652

18.1.1 definitions

Nonrecursively, a tree consists of a set of nodes and a set of directed edges
that connect pairs of nodes. Throughout this text we consider only rooted
trees. A rooted tree has the following properties.

A tree can be
defined nonrecur-
sively as a set of
nodes and a set of
directed edges that
connect them. One node is distinguished as the root.

n

Every node c, except the root, is connected by an edge from exactly
one other node p . Node p is c 's parent , and c is one of p 's children .

n

Parents and chil-
dren are naturally
defined. A directed
edge connects the
parent to the child .

A unique path traverses from the root to each node. The number of
edges that must be followed is the path length .

n

Parents and children are naturally defined. A directed edge connects the par-
ent to the child.

Figure 18.1 illustrates a tree. The root node is A; A 's children are B, C, D,
and E . Because A is the root, it has no parent; all other nodes have parents. For
instance, B 's parent is A . A node that has no children is called a leaf. The
leaves in this tree are C, F, G, H, I, and K . The length of the path from A to K
is 3 (edges); the length of the path from A to A is 0 (edges).

A leaf has no
children.

A tree with N nodes must have N - 1 edges because every node except
the parent has an incoming edge. The depth of a node in a tree is the length
of the path from the root to the node. Thus the depth of the root is always 0,
and the depth of any node is 1 more than the depth of its parent. The height of
a node in a tree is the length of the path from the node to the deepest leaf.
Thus the height of E is 2. The height of any node is 1 more than the height of
its maximum-height child. Thus the height of a tree is the height of the root.

The depth of a node
is the length of the
path from the root
to the node. The
height of a node is
the length of the
path from the node
to the deepest leaf.

figure 18.1
A tree, with height and
depth information

A

Node
A
B
C
D
E
F
G
H
I
J
K

Height
3
1
0
1
2
0
0
0
0
1
0

Depth
0
1
1
1
1
2
2
2
2
2
3

B C D E

F G H I J

K