Java Reference
In-Depth Information
R
A
B
R
A
B
C
D
E
F
C
D
E
F
(A)
(B)
Figure6.13
A dynamic general tree representation with linked lists of child
pointers. (a) The general tree. (b) The tree representation.
6.3.4
Dynamic \Left-Child/Right-Sibling" Implementation
The “left-child/right-sibling” implementation of Section 6.3.2 stores a fixed number
of pointers with each node. This can be readily adapted to a dynamic implemen-
tation. In essence, we substitute a binary tree for a general tree. Each node of the
“left-child/right-sibling” implementation points to two “children” in a new binary
tree structure. The left child of this new structure is the node's first child in the
general tree. The right child is the node's right sibling. We can easily extend this
conversion to a forest of general trees, because the roots of the trees can be con-
sidered siblings. Converting from a forest of general trees to a single binary tree
is illustrated by Figure 6.14. Here we simply include links from each node to its
right sibling and remove links to all children except the leftmost child. Figure 6.15
shows how this might look in an implementation with two pointers at each node.
Compared with the implementation illustrated by Figure 6.13 which requires over-
head of three pointers/node, the implementation of Figure 6.15 only requires two
pointers per node. The representation of Figure 6.15 is likely to be easier to imple-
ment, space efficient, and more flexible than the other implementations presented
in this section.
6.4
K
-ary Trees
K-ary trees are trees whose internal nodes all have exactly K children. Thus,
a full binary tree is a 2-ary tree. The PR quadtree discussed in Section 13.3 is an
example of a 4-ary tree. Because K-ary tree nodes have a fixed number of children,
unlike general trees, they are relatively easy to implement. In general, K-ary trees
