* Aris:
Hello!
This is my problem.
I'm trying to make an inorder traversal algorithm for
a binary tree, not a recursive one, but using a stack.
Till now I got this:
void traverse(tree * p)
{
l: if(p==0) goto s;
push(p);
p=p->l; goto l;
r: visit(p);
p=p->r;
goto l;
s: if(top==0) goto x;
p=pop(); goto r;
x: ;
}
we call this function this way : traverse(root);
My question is :
how can I eliminate goto's?
Everything I've tryed is a mess.
I'll be greatfull if you help me.
I will assume that this is not HOMEWORK. But if it is then an answer
can still be helpful to others. Essentially, transform the code to
something less awful one small step at a time, preserving the code's
effect _exactly_ at each small step.
Let's start with the first label, 'l'. The 'if' there effects a jump
over the following code. So rearrange:
void traverse(tree * p)
{
l: if( p != 0 ) // if(p==0) goto s;
{
push(p);
p = p->l; goto l;
}
s: if( top == 0) goto x;
p = pop(); goto r;
r: visit(p);
p = p->r;
goto l;
x: ;
}
Now you have loop there, so express that as a loop:
void traverse(tree * p)
{
l: while( p != 0 )
{
push(p);
p = p->l;
}
s: if( top == 0) goto x;
p = pop(); goto r;
r: visit(p);
p = p->r;
goto l;
x: ;
}
The 'goto r' has no effect and so can be eliminated, along with the
labels 's' and 'r' which are then no longer referenced:
void traverse(tree * p)
{
l: while( p != 0 )
{
push(p);
p = p->l;
}
if( top == 0 ) goto x;
p = pop();
visit(p);
p = p->r;
goto l;
x: ;
}
That last goto is an outer loop, an infinite one which the goto in the
middle breaks out of:
void traverse(tree * p)
{
for( ;; )
{
while( p != 0 )
{
push(p);
p = p->l;
}
if( top == 0 ) goto x;
p = pop();
visit(p);
p = p->r;
}
x: ;
}
Finally replace the single remaining break-out-of goto with a break:
void traverse(tree * p)
{
for( ;; )
{
while( p != 0 )
{
push(p);
p = p->l;
}
if( top == 0 ) { break; }
p = pop();
visit(p);
p = p->r;
}
}
Now you can start to reason about correctness, e.g., what's that 'top'
in there? Is it perhaps a global modified by 'visit'? If so, then
that's evil and should be fixed, and if not so, then you have
non-working code.
