Java Reference
In-Depth Information
A
B
C
D
E
F
G
H
I
Figure6.17
Sample binary tree for sequential tree implementation examples.
with two (possibly empty) children. Only
null
values will be interpreted as leaf
nodes, and these can be listed explicitly. Such an augmented node list provides
enough information to recover the tree structure.
Example6.5
For the binary tree of Figure 6.17, the corresponding se-
quential representation would be as follows (assuming that '/' stands for
null
):
AB=D==CEG===FH==I==
(6.1)
To reconstruct the tree structure from this node list, we begin by setting
node A to be the root. A's left child will be node B. Node B's left child is
a
null
pointer, so node D must be B's right child. Node D has two
null
children, so node C must be the right child of node A.
To illustrate the difficulty involved in using the sequential tree representation
for processing, consider searching for the right child of the root node. We must first
move sequentially through the node list of the left subtree. Only at this point do
we reach the value of the root's right child. Clearly the sequential representation
is space efficient, but not time efficient for descending through the tree along some
arbitrary path.
Assume that each node value takes a constant amount of space. An example
would be if the node value is a positive integer and
null
is indicated by the value
zero. From the Full Binary Tree Theorem of Section 5.1.1, we know that the size
of the node list will be about twice the number of nodes (i.e., the overhead fraction
is 1/2). The extra space is required by the
null
pointers. We should be able to
store the node list more compactly. However, any sequential implementation must
recognize when a leaf node has been reached, that is, a leaf node indicates the end
of a subtree. One way to do this is to explicitly list with each node whether it is
an internal node or a leaf. If a node X is an internal node, then we know that its
