On Jun 18, 9:13 am, november <[email protected]> wrote:
> please explain the algo for iterative inorder postorder and pre-order
> tree traversals using stack.....(no code only algo plzz :) )
Okay so here is the stripped down code. It does all 3 kinds of
visits. Take your pick.
search_iterative(tree) {
start:
if (tree is not empty) {
preorder visit
push <tree, L0>
tree = tree.left
goto start
L0:
inorder visit
push <tree, L1>
tree = tree.right
goto start
L1:
postorder visit
}
// simulate return to last call site
if (stack not empty) {
<tree, label> = pop()
goto label;
}
}
Now if you want to clean up the gotos, you can start rewriting. I'll
begin by eliminating the gotos at the end by substitution:
search_iterative(tree) {
start:
if (tree is not empty) {
preorder visit
push <tree, L0>
tree = tree.left
goto start
L0:
inorder visit
push <tree, L1>
tree = tree.right
goto start
L1:
postorder visit
}
// simulate return to last call site
end:
if (stack not empty) {
<tree, label> = pop()
if (label = L0) {
inorder visit
push <tree, L1>
tree = tree.right
goto start
}
else {
postorder visit
goto end
}
}
}
Now notice that you don't need the labels L0 an L1 any more, including
the code associated with them. It's all dead. So eliminate it:
search_iterative(tree) {
start:
if (tree is not empty) {
preorder visit
push <tree, L0>
tree = tree.left
goto start
}
end:
if (stack not empty) {
<tree, label> = pop()
if (label = L0) {
inorder visit
push <tree, L1>
tree = tree.right
goto start
}
else {
postorder visit
goto end
}
}
}
Now the top 2 if ()'s can be converted to while loops:
search_iterative(tree) {
start:
while (tree is not empty) {
preorder visit
push <tree, L0>
tree = tree.left
}
while (stack not empty) {
<tree, label> = pop()
if (label = L0) {
inorder visit
push <tree, L1>
tree = tree.right
goto start
}
postorder visit
}
}
Finally, we replace the inner "if" with a loop and flag:
search_iterative(tree) {
do {
restart = false;
while (tree is not empty) {
preorder visit
push <tree, L0>
tree = tree.left
}
while (stack not empty and not restart) {
<tree, label> = pop()
if (label = L0) {
inorder visit
push <tree, L1>
tree = tree.right
restart = true;
}
else {
postorder visit
}
}
} while (restart);
}
I guess you don't like code, but here is code:
#define PUSH(Tree, Site) do { \
stack[sp].tree = Tree; \
stack[sp++].site = Site; } while (0)
#define POP() (tree = stack[--sp].tree, stack[sp].site)
void si(NODE *tree)
{
int restart;
do {
restart = 0;
while (tree) {
printf("preorder %d\n", tree->val);
PUSH(tree, 0);
tree = tree->left;
}
while (sp && !restart) {
if (POP() == 0) {
printf("inorder %d\n", tree->val);
PUSH(tree, 1);
tree = tree->right;
restart = 1;
}
else {
printf("postorder %d\n", tree->val);
}
}
} while (restart);
}
Or if you are willing to tolerate one goto, it's even simpler:
void si(NODE *tree)
{
restart:
while (tree) {
printf("preorder %d\n", tree->val);
PUSH(tree, 0);
tree = tree->left;
}
while (sp) {
if (POP() == 0) {
printf("inorder %d\n", tree->val);
PUSH(tree, 1);
tree = tree->right;
goto restart;
}
printf("postorder %d\n", tree->val);
}
}
Now if you look at this, you can see what it's doing.
--
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.
