Java Reference
In-Depth Information
ROOT
(A)
(B)
Figure6.14
Converting from a forest of general trees to a single binary tree.
Each node stores pointers to its left child and right sibling.
The tree roots are
assumed to be siblings for the purpose of converting.
R
A
R
C
B
D
F
A
B
E
C
D
E
F
(B)
(A)
Figure6.15
A general tree converted to the dynamic “left-child/right-sibling”
representation. Compared to the representation of Figure 6.13, this representation
requires less space.
bear many similarities to binary trees, and similar implementations can be used for
K-ary tree nodes. Note that as K becomes large, the potential number of
null
pointers grows, and the difference between the required sizes for internal nodes
and leaf nodes increases. Thus, as K becomes larger, the need to choose separate
implementations for the internal and leaf nodes becomes more pressing.
Full and complete K-ary trees are analogous to full and complete binary trees,
respectively. Figure 6.16 shows full and complete K-ary trees for K = 3. In
practice, most applications of K-ary trees limit them to be either full or complete.
Many of the properties of binary trees extend to K-ary trees. Equivalent theo-
rems to those in Section 5.1.1 regarding the number of NULL pointers in a K-ary
tree and the relationship between the number of leaves and the number of internal
nodes in a K-ary tree can be derived. We can also store a complete K-ary tree in
an array, using simple formulas to compute a node's relations in a manner similar
to that used in Section 5.3.3.
