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_
{
int val;
struct Node_ *left, *right;
}
Node;
extern void visit(Node *);
Node * const Null = 0;
void traverse(Node *root)
{
Node *curr = root;
Node *stack = Null;
Node *temp;
enum { false, true } 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 (((stack->right) != Null) &&
(stack->val > stack->right->val))
{
/* Pop top of stack and make it current,
** and restore right child pointer. */
temp = curr;
curr = stack;
stack = stack->right;
stack->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;
stack->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;
}
}
}
--
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.
