二叉树算法 [英] Binary tree Algorithm

问题描述

您好！

这是我的问题。

我正在尝试为

a二叉树制作一个inorder遍历算法，而不是一个递归的，但是使用堆栈。

直到现在我得到了这个：


无效遍历（树* p）

{

l：if（p == 0）goto s;

push（p）;

p = p-> l; goto l;

r：访问（p）;

p = p-> r;

goto l;

s：if（top == 0）goto x;

p = pop（）; goto r;

x：;

}


我们用这种方式调用这个函数：traverse（root）;

我的问题是：

我怎么能消除goto'的？

我尝试过的所有东西都是一团糟。

如果你帮助我，我会很高兴。

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.

推荐答案

" ;阿里斯" < NA ****** @ hotmail.com>在留言中写道

news：dm ********** @ usenet.otenet.gr ...

"Aris" <na******@hotmail.com> wrote in message
news:dm**********@usenet.otenet.gr...

你好！
这是我的问题。
我正在尝试为二元树制作一个inorder遍历算法，而不是递归算法，而是使用堆栈。
直到现在我得到了这个：

void traverse（tree * p）
{
l：if（p == 0）goto s;
push（p）;
p = p-> ;升; goto l;
r：访问（p）;
p = p-> r;
goto l;
s：if（top == 0）goto x;
p = pop（）; goto r;
x：;
}
我们用这种方式调用这个函数：traverse（root）;
我的问题是：
我怎么能消除goto'的？

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;

}


如果（顶部）

{

p = pop（）;

访问（p）;

p = p-> r;

}

}而（顶部）;


或类似的东西（未经测试）。


-Mike

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

* Aris：

你好！
这是我的问题。
我正在尝试为二元树制作一个inorder遍历算法，而不是递归算法，而是使用堆栈。
直到现在我得到了这个：

void traverse（tree * p）
{
l：if（p == 0）goto s;
push（p）;
p = p->升; goto l;
r：访问（p）;
p = p-> r;
goto l;
s：if（top == 0）goto x;
p = pop（）; goto r;
x：;
}
我们用这种方式调用这个函数：traverse（root）;
我的问题是：
我怎么能消除goto'的？
我尝试的一切都是一团糟。
如果你帮助我，我会很高兴。

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.

我会假设这不是家庭作业。但如果它是一个答案

仍然可以对其他人有所帮助。从本质上讲，将代码转换为

一次不太可怕的一小步，在每个小步骤中保留代码'

效果_exactly_。


让我们从第一个标签l开始。 'if''会对以下代码产生一个跳跃

。所以重新排列：


无效遍历（树* p）

{

l：if（p！= 0）//如果（p == 0）goto s;

{

push（p）;

p = p-> l; goto l;

}

s：if（top == 0）goto x;

p = pop（）; goto r;

r：访问（p）;

p = p-> r;

goto l;

x：;

}


现在你有循环，所以表示循环：


void遍历（树* p）

{

l：while（p！= 0）

{

push（ p）;

p = p-> l;

}

s：if（top == 0）goto x;

p = pop（）; goto r;

r：访问（p）;

p = p-> r;

goto l;

x：;

}


''转到''没有效果，所以可以消除，同时

标签''''和''r''然后不再被引用：


void traverse（tree * p）

{

l：while（p！= 0）

{

push（p）;

p = p-> l ;

}

if（top == 0）goto x;

p = pop（）;

访问（p）;

p = p-> r;

goto l;

x：;

}


最后一个goto是一个外循环，一个无限的循环，它在

中间的goto突破：


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; < br $>
}

x：;

}


最后替换单个剩余的转出goto休息时间：


无效遍历（树* p）

{

for（;; ）

{

while（p！= 0）

{

push（p）;

p = p-> l;

}

if（top == 0）{break; }

p = pop（）;

访问（p）;

p = p-> r;

}

}


现在你可以开始推理正确性，例如，那是什么''顶''
$ b $那边有吗？这可能是访问的全球修改吗？如果是这样，那么

那是'邪恶的，应该修复，如果不是这样，那么你有

非工作代码。

-

答：因为它弄乱了人们通常阅读文字的顺序。

问：为什么这么糟糕？

A：热门发布。

问：usenet和电子邮件中最烦人的事情是什么？

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?

不仅是一个好的答案，而是面对这个问题的方式

将来。

Gratefull！

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

这篇关于二叉树算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！