Velocity Reviews > C++ > Binary tree Algorithm

# Binary tree Algorithm

Aris
Guest
Posts: n/a

 12-03-2005
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.

Mike Wahler
Guest
Posts: n/a

 12-03-2005

"Aris" <(E-Mail Removed)> wrote in message
news:dmt2lt\$988\$(E-Mail Removed)...
> 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?

do
{
while(p)
{
push(p);
p=p->l;
}

if(top)
{
p = pop();
visit(p);
p = p->r;
}
} while(top);

Or something like that (not tested).

-Mike

Alf P. Steinbach
Guest
Posts: n/a

 12-03-2005
* 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.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Aris
Guest
Posts: n/a

 12-04-2005
Not only a good answer but the way to face this problems
in the future.
Gratefull!

Hans Lohninger
Guest
Posts: n/a

 12-04-2005
A good introduction how to handle trees (and other data structures) can be
found in the free eBook "C++Course". Trees are discussed here:

http://www.vias.org/cppcourse/chap21_01.html

Regards,

Hans

=====================================
Hans Lohninger
EPINA GmbH - Software Development Lohninger
www.lohninger.com
mailto(E-Mail Removed)
fax: +43-2233-541945
======================================

"Aris" <(E-Mail Removed)> wrote in message
news:dmt2lt\$988\$(E-Mail Removed)...
> 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.
>
>
>
>

Victor Bazarov
Guest
Posts: n/a

 12-05-2005
Aris wrote:
> Not only a good answer but the way to face this problems
> in the future.
> Gratefull!

Just a note: it would be useful (or maybe simply more pleasant
to whoever gave you that answer), to have quoted the message
you replied to...

Aris
Guest
Posts: n/a

 12-07-2005
Hello!
Im trying to implement a queue
and I expected my Degueue()
function to return the value of the
key of the node I constructed.
But It does not.
In fact it returns "Empty Queue"
what am I doing wrong?

#include <stdlib.h>
#include <stdio.h>

struct Queue
{
int key;
};

{
ptr->key=data;
Tail=ptr;
}

{
}

else
{
printf("Empty Queue\n"); return 0;
}

free(temp);
return data;
}

int main()
{

printf("%d\n",x);

return 0;

}

Jeff Flinn
Guest
Posts: n/a

 12-07-2005

"Hans Lohninger" <(E-Mail Removed)> wrote in message
news:4392ebff\$0\$28520\$(E-Mail Removed) ...
>A good introduction how to handle trees (and other data structures) can be
>found in the free eBook "C++Course". Trees are discussed here:
>
> http://www.vias.org/cppcourse/chap21_01.html
>

Except it's not really C++ is it.

Jeff

Michael Wild
Guest
Posts: n/a

 12-07-2005
Jeff Flinn wrote:
> "Hans Lohninger" <(E-Mail Removed)> wrote in message
> news:4392ebff\$0\$28520\$(E-Mail Removed) ...
>> A good introduction how to handle trees (and other data structures) can be
>> found in the free eBook "C++Course". Trees are discussed here:
>>
>> http://www.vias.org/cppcourse/chap21_01.html
>>

>
> Except it's not really C++ is it.
>
> Jeff
>
>
>

Since when does c++ have interfaces? (see
http://www.vias.org/cppcourse/chap21_08.html) rather looks like java to
me...

- michael

Ron Natalie
Guest
Posts: n/a

 12-08-2005
Aris wrote:
> Hello!
> Im trying to implement a queue

as part of the language?

Further the code while syntactcally C++ is pretty
poor C++ design.

> {

> int main()
> {
>

head and tail are still null pointers here. You are passing
by value. All Enqueue does is malloc stuff that gets lost.