Assuming your tree is a max-populated left-dominant representation, then any given point in your array at position i
will have children at positions 2*i+1
and 2*i+2
. The trivial walk:
Node Children
===== ===========
ar[0]: ar[1], ar[2]
ar[1]: ar[3], ar[4]
ar[2]: ar[5], ar[6]
ar[3]: ar[7], ar[8]
ar[4]: ar[9], ar[10] etc...
Given this definition, preorder, postorder, and in-order can all be done with simple index forwarding and some checks for your 'occupied' flag. The following templates assume type T
is a structure type that has an 'occupied' member.
template<typename T>
void preorder(const T ar[], size_t i, size_t count, void (&visit)(const T&))
{
if (i>=count || !ar[i].occupied)
return;
visit(ar[i]);
preorder(ar, 2*i+1, count, visit);
preorder(ar, 2*(i+1), count, visit);
}
template<typename T>
void inorder(const T ar[], size_t i, size_t count, void (&visit)(const T&))
{
if (i>=count || !ar[i].occupied)
return;
inorder(ar, 2*i+1, count, visit);
visit(ar[i]);
inorder(ar, 2*(i+1), count, visit);
}
template<typename T>
void postorder(const T ar[], size_t i, size_t count, void (&visit)(const T&))
{
if (i>=count || !ar[i].occupied)
return;
postorder(ar, 2*i+1, count, visit);
postorder(ar, 2*(i+1), count, visit);
visit(ar[i]);
}