Graphics Reference
In-Depth Information
a nonbalanced tree, space still has to be allocated as if the tree were complemented
with extra nodes to make it fully balanced. What is worse, even a single extra node
added to a fully balanced tree will add one full extra level to the tree, doubling its
storage space!
As such, this representation is most useful when the actual node data (its “pay-
load”) is small compared to the combined size of the child pointers, or when the
tree really is fully balanced (or just a few nodes off on the short side from being
fully balanced). For instance, when a hierarchy has been built using a median-based
splitting criterion that guarantees some level of near balance, this could be a useful
representation.
6.6.2
Preorder Traversal Order
Even when no guarantees can be made about the balance of the tree hierarchy, it is
still possible to output the data in a more effective representation. If the tree nodes are
output in preorder traversal order, the left child when present will always immediately
follow its parent. This way, although a link is still needed to point at the right child only
a single bit is needed to indicate whether there is a left child (immediately following
the current node). Figure 6.7 illustrates a binary tree and its nodes output in preorder
traversal order.
A routine taking an ordinary pointer-based tree and outputting it in preorder traver-
sal order into an array is fairly straightforward to implement. The only complication
is in updating the right-link pointers to point at a node location that is unknown at
the time the parent node is written to memory. These can either be handled through
a second pass through the tree or (better) through stacking and backpatching, as in
the following code.
A
B
C
D
E
F
G
H
IJ
K
ABDHE C F
I
JGK
Figure 6.7
Same tree as in Figure 6.6 but with nodes output in preorder traversal order.
Nodes now need a pointer to the right child (shown as an arrow). They also need a bit to
indicate if the node has a left child (which when present always immediately follows the
parent node). Here, this bit is indicated by a gray triangle.
