怎样避开递归算法

① 如何用非递归算法求二叉树的高度

if（T＝＝null）

return0；

intfront＝－1，

rear＝－1；

／／front出队指针

rear入队指针intlast＝0，

level＝0；

／／last每一层的最右指针

（front＝＝last时候一层遍历结束level＋＋）BiTreeQ［Maxsize］；

／／模拟队列Q［＋＋rear］＝T；

BiTreep；

while(front<rear){

p＝Q［＋＋front］；／／开始出队

因为front要赶到lash

实现level＋＋

if(p->lchild)

Q[++rear] = p->lchild;

if(p->rchild)

Q[++rear] = p->rchild;

if（front＝＝last）｛

level＋＋；

last＝rear；／／last指向下层节点｝

｝

(1)怎样避开递归算法扩展阅读

非递归算法思想：

（1）设置一个栈S存放所经过的根结点（指针）信息；初始化S；

（2）第一次访问到根结点并不访问，而是入栈；

（3）中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点；然后中序遍历它的右子树。

（4）当需要退栈时，如果栈为空则结束。

② 编写 快速排序的非递归算法

终于编写出来了，我写了两种，你看看：下面是代码：
/*非递归算法1
??递归算法的开销很大，所以在下编了一个非递归的，算法描述如下：
??A
non-recursive
version
of
quick
sort
using
stack:
??
There
are
2
stacks,
namely
one
which
stores
the
start
of
??a
subarray
and
the
other
which
stores
the
end
of
the
??subarray.
??STEP
1:
while
the
subarray
contains
more
than
one
element
??,i.e.
from??
Do
{
??
SUBSTEP
1.
pivot=Partion(subarray);
??
SUBSTEP
2.
keep
track
of
the
right
half
of
the
current
??subarray
i.e.
push
(pivot+1)
into
stackFrom,
push
(to)
into
stackTo
??
SUBSTEP
3.
go
on
to
deal
with
the
left
half
of
??the
current
subarray
i.e.
to=pivot-1
??
}
??STEP
2:
if(neither
of
the
stacks
is
empty)
??
Get
a
new
subarray
to
deal
with
from
the
stacks.
??
i.e.
start=pop(stackFrom);
to=pop(stackTo);
??STEP
3:
both
stacks
are
empty,
and
array
has
??been
sorted.
The
program
ends.
??
??*/*/
??void
UnrecQuicksort(int
q[],int
low,int
high)
??{stack
s1;<br/>??stacks2;<br/>??
s1.push(low);<br/>??
s2.push(high);<br/>??
int
tl,th,p;<br/>??
while(!s1.empty()
&&
!s2.empty())<br/>??
{tl=s1.top();th=s2.top();<br/>??
s1.pop();s2.pop();<br/>??
if(tl>=th)
continue;<br/>??
p=partition(q,tl,th);<br/>??
s1.push(tl);s1.push(p+1);<br/>??
s2.push(p-1);s2.push(th);<br/>??
}
??}
??
??/*非递归算法2
??要把递归算法改写成非递归算法，可引进一个栈，这个栈的大小取决于递归调用的深度，最
??多不会超过n，如果每次都选较大的部分进栈，处理较短的部分，递归深度最多不超过log2n
??，也就是说快速排序需要的附加存储开销为O（log2n）。
??*/
??void
UnrecQuicksort2(int
q[],int
low,int
high)
??{int
*a;<br/>??
int
top=0,i,j,p;<br/>??
a=new
int[high-low+1];<br/>??
if(a==NULL)
return;<br/>??
a[top++]=low;<br/>??
a[top++]=high;<br/>??
while(top>0)<br/>??
{i=a[--top];<br/>??
j=a[--top];<br/>??
while(j??
{p=partition(q,j,i);<br/>??
if(p-j??
{//先分割前部,后部进栈<br/>??a[top++]=p+1;<br/>??
a[top++]=i;<br/>??
i=p-1;<br/>??
}
??
else
??
{//先分割后部,前部进栈
??a[top++]=j;
??
a[top++]=p-1;
??
j=p+1;
??
}
??
}
??
}
??}
??
??/*打印输出*/
??void
display(int
p[],int
len)
??{for(int
i=0;i??
cout<??}
??
??
??/*测试*/
??int
_tmain(int
argc,
_TCHAR*
argv[])
??{int
a[]={49,65,97,12,23,41,56,14};
??quicksort(a,0,7);
??//UnrecQuicksort(a,0,7);
??
//UnrecQuicksort2(a,0,7);
??display(a,8);
??return
0;
??}
??

③ 二叉树后序遍历非递归算法

#include
<stdio.h>
#include
<stdlib.h>
struct
tree
{
char
data;
struct
tree
*lchild;
struct
tree
*rchild;
};
typedef
struct
tree
*
treptr;
treptr
build(treptr
t)//先序建树
{
char
c;
c=getchar();
if(c=='#')
{
t=NULL;
}
else
{
t=(treptr)malloc(sizeof(struct
tree));
t->data=c;
t->lchild=build(t->lchild);
t->rchild=build(t->rchild);
}
return
t;
}
void
postdorder(treptr
root)//这是递归实现
{
if
(root!=NULL)
{
postdorder(root->lchild);
postdorder(root->rchild);
printf("%c",root->data);
}
}
struct
stack
{
treptr
*top,*base;
};
typedef
struct
stack
*stackptr;
void
init
(stackptr
s)//初始化栈
{
s->base=(treptr*)malloc(sizeof(treptr)*100);
s->top=s->base;
}
void
push(stackptr
s,treptr
t)//入栈
{
*(s->top++)=t;
}
treptr
pop(stackptr
s)//弹出栈顶元素
{
treptr
t;
t=*(--(s->top));
return
t;
}
treptr
gettop(stackptr
s)//取栈顶元素
{
treptr
*l=s->top-1;
return
*(l);
}
void
postorder(treptr
t)//这是非递归后序实现
{
stackptr
s=(stackptr)malloc(sizeof(struct
stack));
treptr
temp=t;
treptr
p;
treptr
lastvist=NULL;
init(s);
p=t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
temp=gettop(s);
if(temp->rchild==NULL||temp->rchild==lastvist)
{
putchar(temp->data);
lastvist=pop(s);
}
else
p=temp->rchild;
}
}
int
main()
{
treptr
t=NULL;
t=build(t);
postdorder(t);
printf("非递归后序遍历\
");
postorder(t);
printf("\
");
return
0;
}
程序如上，可以运行。
我空间中有中序遍历的非递归实现。
不过给你写的是后序遍历的递归实现和非递归实现，它两个输出的结果是一致的。
输入
234##5#6##7##回车
就可以看到结果。
中序遍历及其对应树可以参考我空间中的文章
http://hi..com/huifeng00/blog/item/2ca470f56694f62e730eec39.html

④ 后序遍历的非递归算法是什么

对于树的遍历我们最常用的三种遍历方法分别是前序遍历、中序遍历和后序遍历，使用的方法是深度优先遍历树的每一个节点，这些遍历方法都是使用递归函数来进行实现的。

在数据量大的情况下是比较低效的，原因在于系统帮助我们调用了一个栈并且做了诸如保护现场和恢复现场等复杂的操作。

才使得遍历可以使用非常简单的代码来实现，所以我们可以模仿系统中调用的栈自己可以来写一下栈，模仿其中的过程就可以完成对于三种遍历算法的实现，使用自定义的栈来代替系统栈可以得到效率上的提升，下面是对于后序遍历的非递归算法的实现。

简介

从逆后序遍历与先序遍历的关系中我们可以知道逆后序遍历序列为先序遍历交换左右子树的遍历顺序得到的。

所以我们得到了逆后序序列之后然后逆序就可以得到后序遍历的序列了，所以需要两个栈，第一个栈用来存储先序遍历交换左右子树的遍历的中介结果。