# Binary tree Algorithm

Discussion in 'C++' started by Aris, Dec 3, 2005.

1. ### ArisGuest

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.

Aris, Dec 3, 2005

2. ### Mike WahlerGuest

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

Mike Wahler, Dec 3, 2005

3. ### Alf P. SteinbachGuest

* 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?

Alf P. Steinbach, Dec 3, 2005
4. ### ArisGuest

very good!

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

Aris, Dec 4, 2005
5. ### Hans LohningerGuest

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
fax: +43-2233-541945
======================================

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

Hans Lohninger, Dec 4, 2005
6. ### Victor BazarovGuest

Re: very good!

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...

Victor Bazarov, Dec 5, 2005
7. ### ArisGuest

what's happening in this code?

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;

}

Aris, Dec 7, 2005
8. ### Jeff FlinnGuest

"Hans Lohninger" <> wrote in message
news:4392ebff\$0\$28520\$...
>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

Jeff Flinn, Dec 7, 2005
9. ### Michael WildGuest

Jeff Flinn wrote:
> "Hans Lohninger" <> wrote in message
> news:4392ebff\$0\$28520\$...
>> 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

Michael Wild, Dec 7, 2005
10. ### Ron NatalieGuest

Re: what's happening in this code?

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.

Ron Natalie, Dec 8, 2005
11. ### red floydGuest

Re: what's happening in this code?

Ron Natalie wrote:
> Aris wrote:
>
>> Hello!
>> Im trying to implement a queue

>
>
> as part of the language?

He may know it, but maybe he wants to implement it himself so that he
can understand the concept or possible underlying data structures
better.

However, for production code, go with the Standard Library containers.

red floyd, Dec 8, 2005