Binary tree Algorithm

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

[Mike Wahler]

Re: Binary tree Algorithm


"Aris" <nasos936@hotma il.com> wrote in message
news:dmt2lt$988 $1@usenet.otene t.gr...[color=blue]
> 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?[/color]

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]

Re: Binary tree Algorithm

* Aris:[color=blue]
> 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.[/color]

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]

very good!

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

[Hans Lohninger]

Re: Binary tree Algorithm

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

https://www.lohninger.com

mailto:office@e pinasoft.com
fax: +43-2233-541945
=============== =============== ========

"Aris" <nasos936@hotma il.com> wrote in message
news:dmt2lt$988 $1@usenet.otene t.gr...[color=blue]
> 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.
>
>
>
>[/color]

[Victor Bazarov]

Re: very good!

Aris wrote:[color=blue]
> Not only a good answer but the way to face this problems
> in the future.
> Gratefull![/color]

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]

what's happening in this code?

Hello!
Im trying to implement a queue
using a linked list.
I've made that code
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>

typedef struct Queue * link;
struct Queue
{
link head;
link tail;
link next;
int key;
};

void Enqueue(link Head,link Tail,int data)
{
link ptr=(struct Queue*)malloc(s izeof(struct Queue));
ptr->key=data;
if(Head==0) Head= ptr; else Tail->next=ptr;
Tail=ptr;
}

int Dequeue(link Head,int data)
{
link temp;
if(Head!=0){
data=Head->key;
temp=Head;
Head=Head->next;
}

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

free(temp);
return data;
}

int main()
{
link head=0;
link tail=0;

Enqueue(head,ta il,1);

int x=Dequeue(head, x);
printf("%d\n",x );



return 0;

}

[Jeff Flinn]

Re: Binary tree Algorithm


"Hans Lohninger" <hans@lohninger .com> wrote in message
news:4392ebff$0 $28520$3b214f66 @tunews.univie. ac.at...[color=blue]
>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
>[/color]

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

Jeff

[Michael Wild]

Re: Binary tree Algorithm

Jeff Flinn wrote:[color=blue]
> "Hans Lohninger" <hans@lohninger .com> wrote in message
> news:4392ebff$0 $28520$3b214f66 @tunews.univie. ac.at...[color=green]
>> 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
>>[/color]
>
> Except it's not really C++ is it.
>
> Jeff
>
>
>[/color]

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

- michael

[Ron Natalie]

Re: what's happening in this code?

Aris wrote:[color=blue]
> Hello!
> Im trying to implement a queue
> using a linked list.[/color]

You know C++ already provides queues and linked list
as part of the language?

Further the code while syntactcally C++ is pretty
poor C++ design.
[color=blue]
> void Enqueue(link Head,link Tail,int data)
> {
> link ptr=(struct Queue*)malloc(s izeof(struct Queue));[/color]
[color=blue]
> int main()
> {
> link head=0;
> link tail=0;
>
> Enqueue(head,ta il,1);[/color]

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

[red floyd]

Re: what's happening in this code?

Ron Natalie wrote:[color=blue]
> Aris wrote:
>[color=green]
>> Hello!
>> Im trying to implement a queue
>> using a linked list.[/color]
>
>
> You know C++ already provides queues and linked list
> as part of the language?[/color]

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.