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]

"Aris" <na******@hotma il.com> wrote in message
news:dm******** **@usenet.otene t.gr...

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]

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

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

[Hans Lohninger]

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:of****@e pinasoft.com
fax: [phone]
=============== =============== ========

"Aris" <na******@hotma il.com> wrote in message
news:dm******** **@usenet.otene t.gr...

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]

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]

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]

"Hans Lohninger" <ha**@lohninger .com> wrote in message
news:43******** *************** @tunews.univie. ac.at...

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]

Jeff Flinn wrote:

"Hans Lohninger" <ha**@lohninger .com> wrote in message
news:43******** *************** @tunews.univie. ac.at...

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]

Aris wrote:

Hello!
Im trying to implement a queue
using a linked list.
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.
void Enqueue(link Head,link Tail,int data)
{
link ptr=(struct Queue*)malloc(s izeof(struct Queue)); int main()
{
link head=0;
link tail=0;

Enqueue(head,ta il,1);

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