Java Reference
In-Depth Information
two children (which may be subtrees) immediately follow X in the node list. If X
is a leaf node, then the next node in the list is the right child of some ancestor
of X, not the right child of X. In particular, the next node will be the child of X's
most recent ancestor that has not yet seen its right child. However, this assumes
that each internal node does in fact have two children, in other words, that the
tree is full. Empty children must be indicated in the node list explicitly. Assume
that internal nodes are marked with a prime (
0
) and that leaf nodes show no mark.
Empty children of internal nodes are indicated by '/', but the (empty) children of
leaf nodes are not represented at all. Note that a full binary tree stores no
null
values with this implementation, and so requires less overhead.
Example6.6
We can represent the tree of Figure 6.17 as follows:
A
0
B
0
=DC
0
E
0
G=F
0
HI
(6.2)
Note that slashes are needed for the empty children because this is not a full
binary tree.
Storing n extra bits can be a considerable savings over storing n
null
values.
In Example 6.6, each node is shown with a mark if it is internal, or no mark if it
is a leaf. This requires that each node value has space to store the mark bit. This
might be true if, for example, the node value were stored as a 4-byte integer but
the range of the values sored was small enough so that not all bits are used. An
example would be if all node values must be positive. Then the high-order (sign)
bit of the integer value could be used as the mark bit.
Another approach is to store a separate bit vector to represent the status of each
node. In this case, each node of the tree corresponds to one bit in the bit vector. A
value of '1' could indicate an internal node, and '0' could indicate a leaf node.
Example6.7
The bit vector for the tree if Figure 6.17 (including positions
for the null children of nodes B and E) would be
11001100100
(6.3)
Storing general trees by means of a sequential implementation requires that
more explicit structural information be included with the node list. Not only must
the general tree implementation indicate whether a node is leaf or internal, it must
also indicate how many children the node has. Alternatively, the implementation
can indicate when a node's child list has come to an end. The next example dis-
penses with marks for internal or leaf nodes. Instead it includes a special mark (we
