Java Reference
In-Depth Information
23.8
Binary trees.
As we mentioned earlier, each node in a binary tree has at most two children. They
are called the
left child
and the
right child
.
For example, each tree in Figure 23-6 is a binary tree.
In Figure 23-6a, nodes
B
,
D
, and
F
are left children, and nodes
C
,
E
, and
G
are right children. The
root of this binary tree has two subtrees. The
left subtree
is rooted at
B
and the
right subtree
is
rooted at
C
. Thus, the left subtree of a binary tree is the left subtree of its root; likewise for the
right subtree.
FIGURE 23-6
Three binary trees
(a) Full tree
(b) Complete tree
(c) Tree that is not full
and not complete
A
H
R
I
B
C
J
S
T
D
E
F
G
L
M
U
K
N
V
W
Left children: B, D, F
Right children: C, E, G
O
P
Y
Q
X
Every subtree in a binary tree is also a binary tree. In fact, we can think of a binary tree recur-
sively, as follows:
Note:
A binary tree is either empty or has the following form:
Root
T
left
T
right
where
T
left
and
T
right
are binary trees.
When a binary tree of height
h
has all of its leaves at level
h
and every nonleaf (parent) has
exactly two children, the tree is said to be
full
.
Figure 23-6a shows a full binary tree. If all levels of
a binary tree but the last contain as many nodes as possible, and the nodes on the last level are filled
in from left to right—as in Figure 23-6b—the tree is
complete
.
The binary tree in Figure 23-6c is
neither full nor complete. In this case, a node can have a left child but no right child (for example,
node
S
), or a right child but no left child (for example, node
U
).
Note:
All leaves in a full binary tree are on the same level and every nonleaf has exactly
two children. A complete binary tree is full to its next-to-last level, and its leaves on the last
level are filled from left to right. Binary trees are used extensively, and these special trees will
be important to our later discussions.
