Working version, with test code.
Limited to trees where node key values are unique. Seems to have the
advantage of better access locality. But I suspect the average time
per node is typically greater than for Morris Traversal.
typedef struct Node_
{
unsigned val;
struct Node_ *left, *right;
}
Node;
extern void visit(Node *);
Node * const Null = 0;
typedef enum { false, true } bool;
void traverse(Node *root)
{
Node *curr = root;
Node *stack = Null;
Node *temp;
bool popped = false;
for ( ; ; )
{
if (!popped)
while (curr->left != Null)
{
/* Use left pointer to push current node onto
** linked list stack, and make left child
** current. */
temp = stack;
stack = curr;
curr = stack->left;
stack->left = temp;
}
else
popped = false;
visit(curr);
if (curr->right == Null)
{
if (stack == Null)
/* Traversal done. */
break;
while (curr->val > stack->val)
{
/* Pop top of stack and make it current,
** and restore right child pointer. */
temp = curr;
curr = stack;
stack = stack->right;
curr->right = temp;
if (stack == Null)
/* Traversal done. */
break;
}
if (stack == Null)
/* Traversal done. */
break;
/* Pop top of stack and make it current,
** and restore left child pointer. */
temp = curr;
curr = stack;
stack = stack->left;
curr->left = temp;
popped = true;
}
else
{
/* Use right pointer to push current node onto
** linked list stack, and make right child
** current. */
temp = stack;
stack = curr;
curr = stack->right;
stack->right = temp;
}
}
}
#define N 14
Node n[N];
Node *first(unsigned base, unsigned count)
{
unsigned i;
if (count == 0)
return(Null);
n[base].left = Null;
n[base].right = Null;
for (i = 1; i < count; ++i)
{
n[base + i].left = n + base + i - 1;
n[base + i].right = Null;
}
return(n + base + count - 1);
}
void range(Node *sub, unsigned *base, unsigned *count)
{
if (sub == Null)
*count = 0;
else
{
Node *ll = sub, *rr = sub;
while (ll->left != Null)
ll = ll->left;
while (rr->right != Null)
rr = rr->right;
*base = ll - n;
*count = rr - ll + 1;
}
}
bool next(Node **sub)
{
if (*sub == Null)
return(false);
if (!next(&((*sub)->left)))
{
unsigned base, count;
if (next(&((*sub)->right)))
{
range((*sub)->left, &base, &count);
(*sub)->left = first(base, count);
}
else if ((*sub)->left == Null)
return(false);
else
{
unsigned r = *sub - n - 1;
range(*sub, &base, &count);
n[r].left = first(base, r - base);
n[r].right = first(r + 1, count - (r - base) - 1);
*sub = n + r;
}
}
return(true);
}
unsigned inc;
#include <stdio.h>
#include <stdlib.h>
void visit(Node *n)
{
if (n->val != inc)
{
printf("FAIL %u %u\n", n->val, inc);
exit(1);
}
++inc;
}
void test(unsigned count)
{
unsigned tree_count = 0;
Node *root = first(0, count);
do
{
inc = 0;
traverse(root);
if (inc != count)
{
printf("FAIL2 %u %u\n", inc, count);
exit(1);
}
++tree_count;
}
while (next(&root));
printf("TEST: nodes=%u trees=%u\n", count, tree_count);
}
int main(void)
{
unsigned i;
for (i = 0; i < N; ++i)
n[i].val = i;
test(1);
test(2);
test(3);
test(N);
printf("SUCCESS\n");
return(0);
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
