Java Reference
In-Depth Information
A
B
C
D
E
F
G
H
I
Figure5.1
A binary tree. Node A is the root. Nodes B and C are A's children.
Nodes B and D together form a subtree. Node B has two children: Its left child
is the empty tree and its right child is D. Nodes A, C, and E are ancestors of G.
Nodes D, E, and F make up level 2 of the tree; node A is at level 0. The edges
from A to C to E to G form a path of length 3. Nodes D, G, H, and I are leaves.
Nodes A, B, C, E, and F are internal nodes. The depth of I is 3. The height of this
tree is 4.
root of the tree, while the root is the ancestor of all nodes. The depth of a node M
in the tree is the length of the path from the root of the tree to M. The height of a
tree is one more than the depth of the deepest node in the tree. All nodes of depth d
are at level d in the tree. The root is the only node at level 0, and its depth is 0. A
leaf node is any node that has two empty children. An internal node is any node
that has at least one non-empty child.
Figure 5.1 illustrates the various terms used to identify parts of a binary tree.
Figure 5.2 illustrates an important point regarding the structure of binary trees.
Because all binary tree nodes have two children (one or both of which might be
empty), the two binary trees of Figure 5.2 are not the same.
Two restricted forms of binary tree are sufficiently important to warrant special
names. Each node in a full binary tree is either (1) an internal node with exactly
two non-empty children or (2) a leaf. A complete binary tree has a restricted shape
obtained by starting at the root and filling the tree by levels from left to right. In the
complete binary tree of height d, all levels except possibly level d1 are completely
full. The bottom level has its nodes filled in from the left side.
Figure 5.3 illustrates the differences between full and complete binary trees.
1
There is no particular relationship between these two tree shapes; that is, the tree of
Figure 5.3(a) is full but not complete while the tree of Figure 5.3(b) is complete but
1
While these definitions for full and complete binary tree are the ones most commonly used, they
are not universal. Because the common meaning of the words “full” and “complete” are quite similar,
there is little that you can do to distinguish between them other than to memorize the definitions. Here
is a memory aid that you might find useful: “Complete” is a wider word than “full,” and complete
binary trees tend to be wider than full binary trees because each level of a complete binary tree is as
wide as possible.
