二叉樹非遞歸先序遍歷演算法
Ⅰ 二叉樹的遍歷非遞歸演算法中應注意哪些問題
先序非遞歸演算法
【思路】
假設：T是要遍歷樹的根指針，若T != NULL
對於非遞歸演算法，引入棧模擬遞歸工作棧，初始時棧為空。
問題：如何用棧來保存信息，使得在先序遍歷過左子樹後，能利用棧頂信息獲取T的右子樹的根指針？
方法1：訪問T->data後，將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應扮談彎為T，出棧，再先序遍歷T的右子樹。
方法2：訪問T->data後，將T->rchild入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T->rchild，出棧，遍歷以該指針為根的子樹。
【演算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基於方法一，流程圖如右，當型循環
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【演算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基於方法二，流程圖如右，當型循環
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
進一步考慮：對於處理流程中的循環體的直到型、當型+直到型的實現。
中序非遞歸演算法
【思路】
T是要遍歷樹的根指針，中序遍歷要求廳悶在遍歷完左子樹後，訪問根，再遍歷右子樹。
問題：如何用棧來保存信息，使得在中序遍歷過左子樹後，能利用棧頂信息獲取T指針？
方法：先將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，出棧，訪問T->data，再中序遍歷T的右子樹。
【演算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程圖如右，當型循環
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
進一步考慮：對於處理流程中的循環體的直到型、當型+直到型的實現。
後序非遞歸演算法
【思路】
T是要遍歷樹的根指針，後序遍歷要求在遍歷完左右子樹後，再訪問根。需要判斷根結點的左右子樹是否均遍歷過。
可採用標記法侍升，結點入棧時，配一個標志tag一同入棧(0：遍歷左子樹前的現場保護，1：遍歷右子樹前的現場保護)。
首先將T和tag(為0)入棧，遍歷左子樹；返回後，修改棧頂tag為1，遍歷右子樹；最後訪問根結點。
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【演算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程圖如右，當型循環
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 設置棧頂標記
T = GetTopPointer(S); // 取棧頂保存的指針
T = T->rchild;
}else break;
}
}
Ⅱ 二叉樹先序非遞歸遍歷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");
}
Ⅲ 非遞歸的二叉樹前序遍歷演算法有什麼用途
遞歸和非遞歸只是解決問題的方法的不同，本質還是一樣的。
2. 遞歸演算法相對於非遞歸演算法來說效率通常都會更低
2.1 遞歸演算法會有更多的資源需要壓棧和出棧操作（不僅僅是參數，還有函數地址等）
2.2 由於編譯器對附加的一些棧保護機制會導致遞歸執行的更加低效
3. 使用循環代替遞歸演算法，通常可以獲得更好的執行效率和空間效率，在二叉樹層次較深的情況下，採用非遞歸方式遍歷能夠有效的提升遍歷的性能。
Ⅳ 二叉樹前序遍歷法舉例!急急急！！！
二叉樹的三種金典遍歷法
1.前序遍歷法：
前序遍歷（DLR）
前序遍歷（DLR）
前序遍歷首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
若二叉樹為空則結束返回，否則：
（1）訪問根結點
（2）前序遍歷左子樹
（3）前序遍歷右子樹
注意的是：遍歷左右子樹時仍然採用前序遍歷方法。
如上圖所示二叉樹
前序遍歷，也叫先根遍歷，遍歷的順序是，根，左子樹，右子樹
遍歷結果：ABDECF
中序遍歷，也叫中根遍歷，順序是左子樹，根，右子樹
遍歷結果：DBEAFC
後序遍歷，也叫後根遍歷，遍歷順序，左子樹，右子樹，根
遍歷結果：DEBFCA
2.中序遍歷法：
中序遍歷
中序遍歷（LDR）
中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，再訪問根結點，最後遍歷右子樹。即：
若二叉樹為空則結束返回，否則：
（1）中序遍歷左子樹
（2）訪問根結點
（3）中序遍歷右子樹。
注意的是：遍歷左右子樹時仍然採用中序遍歷方法。
3.後序遍歷法：
後序遍歷
簡介
後序遍歷是二叉樹遍歷的一種。後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹三者中，首先遍歷左子樹，然後遍歷右子樹，最後遍歷訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點。後序遍歷有遞歸演算法和非遞歸演算法兩種。
遞歸演算法
演算法描述：
（1）若二叉樹為空，結束
（2）後序遍歷左子樹
（3）後序遍歷右子樹
（4）訪問根結點
偽代碼
PROCEDUREPOSTRAV(BT)
IFBT<>0THEN
{
POSTRAV(L(BT))
POSTRAV(R(BT))
OUTPUTV(BT)
}
RETURN
c語言描述
structbtnode
{
intd;
structbtnode*lchild;
structbtnode*rchild;
};
voidpostrav(structbtnode*bt)
{
if(bt!=NULL)
{
postrav(bt->lchild);
postrav(bt->rchild);
printf("%d",bt->d);
}
}
非遞歸演算法
演算法1（c語言描述）：
voidpostrav1(structbtnode*bt)
{
structbtnode*p;
struct
{
structbtnode*pt;
inttag;
}st[MaxSize];
}
inttop=-1;
top++;
st[top].pt=bt;
st[top].tag=1;
while(top>-1)/*棧不為空*/
{
if(st[top].tag==1)/*不能直接訪問的情況*/
{
p=st[top].pt;
top--;
if(p!=NULL)
{
top++;/*根結點*/
st[top].pt=p;
st[top].tag=0;
top++;/*右孩子結點*/
st[top].pt=p->p->rchild;
st[top].tag=1;
top++;/*左孩子結點*/
st[top].pt=p->lchild;
st[top].tag=1;
}
}
if(st[top].tag==0)/*直接訪問的情況*/
{
printf("%d",st[top].pt->d);
top--;
}
}
}
演算法2：
voidpostrav2(structbtnode*bt)
{
structbtnode*st[MaxSize],*p;
intflag,top=-1;
if(bt!=NULL)
{
do
{
while(bt!=NULL)
{
top++;
st[top]=bt;
bt=bt->lchild;
}
p=NULL;
flag=1;
while(top!=-1&&flag)
{
bt=st[top];
if(bt->rchild==p)
{
printf("%d",bt->d);
top--;
p=bt;
}
else
{
bt=bt->rchild;
flag=0;
}
}
}while(top!=-1)
printf(" ");
}
}
老曹回答必屬佳作記得給分謝謝合作！
