Graphics Reference
In-Depth Information
A
B
C
D
E
F
G
H
IJ
K
2
i
+ 2
AB CDE F
0
G
H
IJ
K
i
2
i
+ 1
Figure 6.6
A binary tree (top) stored using a pointerless array representation (bottom).
Children of node at array position
i
can be found at positions 2
i
+ 1 and 2
i
+ 2. Note
wasted memory (shown in gray).
Given this setup, it is easy to verify that being at the node stored at
array[i]
the corresponding left child to the node will be found at
array[2*i+1]
and its right
child at
array[2*i+2]
. Consequently, instead of representing the tree using nodes
containing left and right pointers to the node's children it is possible to completely
remove all pointers and store the pointerless nodes in an array in the manner just
described (Figure 6.6). Knowing this child-indexing rule, the actual remapping can
effectively be written as a simple recursive routine.
// Given a tree t, outputs its nodes in breadth-first traversal order
// into the node array n. Call withi=0.
void BreadthFirstOrderOutput(Tree *t, Tree n[], int i)
{
// Copy over contents from tree node to breadth-first tree
n[i].nodeData = t-
>
nodeData;
// If tree has a left node, copy its subtree recursively
if (t-
>
left)
BreadthFirstOrderOutput(t-
>
left, n,2*i+1);
// Ditto if it has a right subtree
if (t-
>
right)
BreadthFirstOrderOutput(t-
>
right, n,2*i+2);
}
When the tree is perfectly balanced (as the assumed complete tree would be),
this saves memory space and pointer reads during tree traversal. Unfortunately, for
