Graphics Reference
In-Depth Information
// Given a tree t, outputs its nodes in preorder traversal order
// into the node array n. Call withi=0.
int PreorderOutput(Tree *t, Tree n[], int i)
{
// Implement a simple stack of parent nodes.
// Note that the stack pointer 'sp' is automatically reset between calls
const int STACK_SIZE = 100;
static int parentStack[STACK_SIZE];
static int sp = 0;
// Copy over contents from tree node to PTO tree
n[i].nodeData = t->nodeData;
// Set the flag indicating whether there is a left child
n[i].hasLeft = t->left != NULL;
// If node has right child, push its index for backpatching
if (t- > right) {
assert(sp < STACK_SIZE);
parentStack[sp++] = i;
}
// Now recurse over left part of tree
if (t- > left)
i = PreorderOutput(t- > left, n,i+1);
if (t- > right) {
// Backpatch right-link of parent to point to this node
int p = parentStack[--sp];
n[p].rightPtr = &n[i + 1];
// Recurse over right part of tree
i = PreorderOutput(t- > right, n,i+1);
}
// Return the updated array index on exit
return i;
}
In addition to reducing the needed number of child pointers by half, this represen-
tation also has the benefit of being quite cache friendly. The left child is very likely
already in cache, having been fetched at the same time as its parent, making traversal
more efficient.
6.6.3 Offsets Instead of Pointers
A typical tree implementation uses (32-bit) pointers to represent node child links.
However, for most trees a pointer representation is overkill. More often than not, by
 
Search WWH ::




Custom Search