Java Reference
In-Depth Information
INDEX VAL PAR
R
0
R
1
3
1
A
0
2
4
6
A
B
2
C
1
3
B
0
5
C
D
E
F
4
D
1
5
F
3
6
E
1
7
Figure6.9
The “list of children” implementation for general trees. The col-
umn of numbers to the left of the node array labels the array indices. The column
labeled “Val” stores node values. The column labeled “Par” stores indices (or
pointers) to the parents. The last column stores pointers to the linked list of chil-
dren for each internal node. Each element of the linked list stores a pointer to one
of the node's children (shown as the array index of the target node).
ADT operations can be implemented by reading a value directly from the node.
If two trees are stored within the same node array, then adding one as the subtree
of the other simply requires setting three pointers. Combining trees in this way
is illustrated by Figure 6.11. This implementation is more space efficient than the
“list of children” implementation, and each node requires a fixed amount of space
in the node array.
6.3.3
Dynamic Node Implementations
The two general tree implementations just described use an array to store the col-
lection of nodes. In contrast, our standard implementation for binary trees stores
each node as a separate dynamic object containing its value and pointers to its two
children. Unfortunately, nodes of a general tree can have any number of children,
and this number may change during the life of the node. A general tree node imple-
mentation must support these properties. One solution is simply to limit the number
of children permitted for any node and allocate pointers for exactly that number of
children. There are two major objections to this. First, it places an undesirable
limit on the number of children, which makes certain trees unrepresentable by this
implementation. Second, this might be extremely wasteful of space because most
nodes will have far fewer children and thus leave some pointer positions empty.
