怎樣避開遞歸演算法

① 如何用非遞歸演算法求二叉樹的高度

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

④ 後序遍歷的非遞歸演算法是什麼

對於樹的遍歷我們最常用的三種遍歷方法分別是前序遍歷、中序遍歷和後序遍歷，使用的方法是深度優先遍歷樹的每一個節點，這些遍歷方法都是使用遞歸函數來進行實現的。

在數據量大的情況下是比較低效的，原因在於系統幫助我們調用了一個棧並且做了諸如保護現場和恢復現場等復雜的操作。

才使得遍歷可以使用非常簡單的代碼來實現，所以我們可以模仿系統中調用的棧自己可以來寫一下棧，模仿其中的過程就可以完成對於三種遍歷演算法的實現，使用自定義的棧來代替系統棧可以得到效率上的提升，下面是對於後序遍歷的非遞歸演算法的實現。

簡介

從逆後序遍歷與先序遍歷的關系中我們可以知道逆後序遍歷序列為先序遍歷交換左右子樹的遍歷順序得到的。

所以我們得到了逆後序序列之後然後逆序就可以得到後序遍歷的序列了，所以需要兩個棧，第一個棧用來存儲先序遍歷交換左右子樹的遍歷的中介結果。