遍歷二叉樹非遞歸演算法
A. 先序便利二叉樹非遞歸演算法如何理解
遞歸方式：先訪問根，再訪問左子樹（遞歸），再訪問右子樹（遞歸）
非遞歸：
當前節點=ROOT;
循環（當前節點不為空）
訪問當前節點。--先根，而且處理完後不在需要
如果有右子樹，push (右子樹）-- 表明在左子樹全部處理完後再處理
如果有左子樹，當前節點為左子樹，continue - 表明優先處理左子樹
如果沒有子樹，當前節點=pop()，continue - 表明一顆子樹已經處理完了，需要從堆棧裡面把以前記得需要處理的再拿出來。
總的來說，非遞歸演算法是利用堆棧，將不是馬上要處理的東西放到堆棧裡面，當需要處理的東西不能直接索引的時候。從堆棧中一個再挖出來處理。
B. 二叉樹的遍歷演算法
這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
1.先序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//訪問根結點
p=p->rchild;
//通過下一次循環實現右子樹遍歷
}//endif
}//endwhile
}//InOrderUnrec
3.後序遍歷非遞歸演算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍歷左子樹
{
x.ptr
=
p;
x.tag
=
L;
//標記為左子樹
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag為R，表示右子樹訪問完畢，故訪問根結點
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec
C. 二叉樹中序遍歷的非遞歸演算法
推薦這篇文章，把二叉樹的前序、中序和後續的遞歸和非遞歸演算法都講了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html
D. 先序遍歷二叉樹的非遞歸演算法
InitStack(S);//初始化棧
p=T;//取棧頂
while(P||!StackEmpty(S)){
//P存在或者棧非空
if(p)
{
//p非空，即左子樹或者右子樹存在
Push(S,p);
//將左子樹入棧
p=p->lchild;
//取下一個左子樹
}
else{
Pop(S,p);
//出棧，相當於先序遍歷了，因為左子樹都TMD入棧了，現在反向輸出
p=p->rchild;
//彈出一個左子樹，就同時取其右子樹右子樹，然後又跳到這個if的最開頭那裡，p存在的那個分支。接下來再取右子樹的左子樹
}
}
//其實，用遞歸也許你更能理解一些。但是，遞歸本質上也是壓棧，只不過是程序壓棧，還不如這個效率高
E. 二叉樹先序非遞歸遍歷c語言演算法
#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //棧的初始長度
#define STACKINCREMENT 5 //棧的追加長度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉樹結點定義
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 鏈棧結點定義top棧頂 base棧底 且棧元素是指向二叉樹結點的二級指針
//建立一個空棧
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //棧底指向開辟空間
if(!s->base) exit(1); //拋出異常
s->top=s->base; //棧頂=棧尾 表示棧空
s->stacksize=STACK_INIT_SIZE; //棧長度為開辟空間大小
return 1;
}
//進棧
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果棧滿 追加開辟空間
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //拋出異常
s->top=s->base+s->stacksize; //感覺這一句沒用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //進棧 棧頂後移
return 1;
}
//出棧
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //棧空 返回0
--s->top;*e=*(s->top); //棧頂前移 取出棧頂元素給e
return 1;}
//取棧頂
int gettop(sqstack *s,bitree **e) //去棧頂元素 注意top指向的是棧頂的後一個
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非遞歸-----先序建立二叉樹----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上這一句為s 初始化開辟空間
ch=getchar();
if(ch!='#'&&ch!='\n') /* 輸入二叉樹先序順序 是以完全二叉樹的先序順序
不是完全二叉樹的把沒有的結點以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根節點進棧
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 驟
return ht;
}
else return NULL;
}
/*--------------------------遞歸---------先序建立二叉樹-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序輸入二叉樹中的結點的值（一個字元），空格字元表示空樹，
//構造二叉鏈表表示二叉樹
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根結點
CreateBiTree(&(*T)->lchild); //構造左子樹
CreateBiTree(&(*T)->rchild); //構造右子樹
}
}
/*--------------------------非遞歸-------中序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------中序建立二叉樹-------------------------------*/
/*--------------------------非遞歸-------後序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------後序建立二叉樹-------------------------------*/
/*-----------------------非遞歸------先序輸出二叉樹------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非遞歸-----中序輸出二叉樹----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非遞歸----後序遍歷二叉樹----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r結點表示訪問了右子樹 代替標志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//層次遍歷二叉樹 用隊列 哈哈以後做
/*-------------------------------主過程-------------------------------*/
int main()
{bitree *ht;
printf("先序非遞歸建立一個二叉樹:");
if((ht=createprebitree())!=NULL) //非遞歸建立
//CreateBiTree(&ht);
//if(ht!=NULL) //遞歸建立
{
printf("先序遍歷輸出二叉樹:");
preordertraverse(ht);
putchar('\n');
printf("中序遍歷輸出二叉樹:");
inordertraverse(ht);
putchar('\n');
printf("後序遍歷輸出二叉樹:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉樹\n");
}
F. 二叉樹中序遍歷非遞歸演算法(c語言實現）
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define null 0
struct node
{
char data;
struct node *lchild;
struct node *rchild;
};
//先序，中序 建樹
struct node *create(char *pre,char *ord,int n)
{
struct node * head;
int ordsit;
head=null;
if(n<=0)
{
return null;
}
else
{
head=(struct node *)malloc(sizeof(struct node));
head->data=*pre;
head->lchild=head->rchild=null;
ordsit=0;
while(ord[ordsit]!=*pre)
{
ordsit++;
}
head->lchild=create(pre+1,ord,ordsit);
head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return head;
}
}
//中序遞歸遍歷
void inorder(struct node *head)
{
if(!head)
return;
else
{
inorder(head->lchild );
printf("%c",head->data );
inorder(head->rchild );
}
}
//中序非遞歸遍歷
void inorder1(struct node *head)
{
struct node *p;
struct node *stack[20];
int top=0;
p=head;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
printf("%c ",p->data );
p=p->rchild ;
}
}
//主函數
int main()
{
struct node * head;
char pre[30],ord[30];
int n;
gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("\n");
inorder1(head);
printf("\n");
}
//測試事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/
幾個月前自己編寫，原版
vc++ 6.0實驗通過
怎麼樣，老闆，第一次上網路知道，好激動
給點面子
給分！給分啊
G. C#的二叉樹中序遍歷非遞歸演算法求詳細解釋！
object e = null; //聲明一個變數存放地址
SqStack S = new SqStack(); //聲明一個棧，用來存放遍歷過程中非末級節點
TreeNode p = t; //聲明一個節點變數p 接收函數傳來的參數 t
while (p != null || !S.SqStackEmpty()) //從跟節點開始遍歷，只要 p！=null （當前該節點還有子節點） 或者 棧 S 沒用清空，循環執行下去。
{
if (p != null)
{
S.SqStackPush(p); 該節點有子節點，先把該節點保存入棧，（棧是後進先出，正好先遍歷完子節點才遍歷父節點的控製作用，棧的最底部存的是根節點，最後才彈出遍歷，遍歷完後，!S.SqStackEmpty() 就不成立了，while循環結束）
p = p.left; // 上一步p變數的節點壓入棧保存後，轉而獲取左邊子節點，繼續循環，如果這是p=null，也就是剛壓入棧的節點沒有子節點，開始執行 else 里的語句
}
else
{
S.SqStackPop(ref e); //彈出剛壓入棧的節點，存放到 e ref e 是指存放該節點的地址
p = (TreeNode)e; 類型強制轉化成 節點類型，因為 e 聲明的是
object類型。付值給p，
Console.Write(p.data + " "); //輸出p的數據。
p = p.right; //轉而讀取該節點右邊的樹，開始新的循環。
}
H. 二叉樹的非遞歸遍歷有什麼優點
遞歸和非遞歸只是解決問題的方法的不同，本質還是一樣的。
2. 遞歸演算法相對於非遞歸演算法來說效率通常都會更低
2.1 遞歸演算法會有更多的資源需要壓棧和出棧操作（不僅僅是參數，還有函數地址等）
2.2 由於編譯器對附加的一些棧保護機制會導致遞歸執行的更加低效
3. 使用循環代替遞歸演算法，通常可以獲得更好的執行效率和空間效率，在二叉樹層次較深的情況下，採用非遞歸方式遍歷能夠有效的提升遍歷的性能。
I. 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此時棧已空，就有問題
}
pBiNode = pBiNode->rchild;
}
return 0;
}
J. 二叉樹後序遍歷（非遞歸）
一，大循環中的第一個循環，當前節點一直往左走一直走到頭，並且把走過的節點壓棧，這個循環遍歷完成後，棧裡面都是左邊走過但是右邊還沒有走過的節點
二，從最左邊那個沒有更左的那個節點，它位於棧頂，因為這時棧頂不是一個右節點，第二個循環跳過，然後把棧頂結點的右節點標記為r並以此作為根節點重復之前的操作
回溯：
因為一直往下層走，總會遇到既沒有左節點有沒有右節點的節點，就是葉子節點，就開始往回退 取他的右節點，取之前會把該節點標記為r，但是他沒有右節點，為null，就會跳過第一個循環，來到第二個，那麼這個葉子就從棧中pop掉，新的棧頂結點是那個葉子的父節點，如果沒有右節點，那他就成了葉子，更簡單，如果有右節點，那麼繼續二
一步一步推就是這樣子，需要考慮所有情況，會把問題想復雜，但是利用遞歸的思想就好想了
參考遞歸演算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一個函數就是第一個小循環，只走左邊，然後把新得到的節點作為根節點，繼續調用第一個函數，得到左節點，然後再作為根節點，直到左節點為空；
第二個函數就是最後一個if，非遞歸演算法中是從棧頂取，就是左邊走過了的節點，相當於遞歸中，第一個函數執行完已經返回，然後取他的右節點作為根節點，繼續遞歸
以上回答你滿意么？