1 遞歸算法
算法的遞歸定義是：
若2叉樹為空，則遍歷結(jié)束；否則
⑴ 中序遍歷左子樹(遞歸調(diào)用本算法)；
⑵ 訪問根結(jié)點；
⑶ 中序遍歷右子樹(遞歸調(diào)用本算法)。
中序遍歷的遞歸算法
void InorderTraverse(BTNode *T)
{ if (T==NULL)
return；
InorderTraverse(T->Lchild) ;
visit(T->data) ; /* 訪問根結(jié)點 */
InorderTraverse(T->Rchild) ;
} 2 非遞歸算法（略）
設(shè)T是指向2叉樹根結(jié)點的指針變量，非遞歸算法是：
若2叉樹為空，則返回；否則，令p=T
⑴ 當p不為空，p進棧， p=p->Lchild ；
⑵ 否則(即p為空)，退棧到p，訪問p所指向的結(jié)點；
⑶ p=p->Rchild ，轉(zhuǎn)(1)；
直到棧空為止。
算法實現(xiàn)：
#define MAX_STACK_SIZE 50
void InorderTraverse( BTNode *T)
{ BTNode *Stack[MAX_STACK_SIZE ] ,*p=T ;
int top=0 , bool=1 ;
if (T==NULL) printf(“ Binary Tree is Empty!
”) ;
else { do
{ while (p!=NULL)
{ stack[++top]=p ; p=p->Lchild ; }
if (top==0) bool=0 ;
else { p=stack[top] ; top-- ;
visit( p->data ) ; p=p->Rchild ; }
} while (bool!=0) ;
}
}
1 遞歸算法
算法的遞歸定義是：
若2叉樹為空，則遍歷結(jié)束；否則
⑴ 后序遍歷左子樹(遞歸調(diào)用本算法)；
⑵ 后序遍歷右子樹(遞歸調(diào)用本算法) ；
⑶ 訪問根結(jié)點 。
后序遍歷的遞歸算法
void PostorderTraverse(BTNode *T)
{ if (T!=NULL)
{ PostorderTraverse(T->Lchild) ;
PostorderTraverse(T->Rchild) ;
visit(T->data) ; /* 訪問根結(jié)點 */
}
}
遍歷2叉樹的算法中基本操作是訪問結(jié)點，因此，不管是哪一種次序的遍歷，對有n個結(jié)點的2叉樹，其時間復雜度均為O(n) 。
2 非遞歸算法（略）
在后序遍歷中，根結(jié)點是最后被訪問的。因此，在遍歷進程中，當搜索指針指向某1根結(jié)點時，不能立即訪問，而要先遍歷其左子樹，此時根結(jié)點進棧。當其左子樹遍歷完后再搜索到該根結(jié)點時，還是不能訪問，還需遍歷其右子樹。所以，此根結(jié)點還需再次進棧，當其右子樹遍歷完后再退棧到到該根結(jié)點時，才能被訪問。
因此，設(shè)立1個狀態(tài)標志變量tag ：
其次，設(shè)兩個堆棧S1、S2 ，S1保存結(jié)點，S2保存結(jié)點的狀態(tài)標志變量tag 。S1和S2共用1個棧頂指針。
設(shè)T是指向根結(jié)點的指針變量，非遞歸算法是：
若2叉樹為空，則返回；否則，令p=T；
⑴ 第1次經(jīng)過根結(jié)點p，不訪問：
p進棧S1 ， tag 賦值0，進棧S2，p=p->Lchild 。
⑵ 若p不為空，轉(zhuǎn)(1)，否則，取狀態(tài)標志值tag ：
⑶ 若tag=0：對棧S1，不訪問，不出棧；修改S2棧頂元素值(tag賦值1) ，取S1棧頂元素的右子樹，即p=S1[top]->Rchild ，轉(zhuǎn)(1)；
⑷ 若tag=1：S1退棧，訪問該結(jié)點；
直到棧空為止。
算法實現(xiàn)：
#define MAX_STACK_SIZE 50
void PostorderTraverse( BTNode *T)
{ BTNode *S1[MAX_STACK_SIZE ] ,*p=T ;
int S2[MAX_STACK_SIZE ] , top=0 , bool=1 ;
if (T==NULL) printf(“Binary Tree is Empty!
”) ;
else { do
{ while (p!=NULL)
{ S1[++top]=p ; S2[top]=0 ;
p=p->Lchild ;
}
if (top==0) bool=0 ;
else if (S2[top]==0)
{ p=S1[top]->Rchild ; S2[top]=1 ; }
else
{ p=S1[top] ; top-- ;
visit( p->data ) ; p=NULL ;
/* 使循環(huán)繼續(xù)進行而不至于死循環(huán) */ }
} while (bool!=0) ;
}}
層次遍歷2叉樹，是從根結(jié)點開始遍歷，按層次次序“自上而下，從左至右”訪問樹中的各結(jié)點。
為保證是按層次遍歷，必須設(shè)置1個隊列。
設(shè)T是指向根結(jié)點的指針變量，層次遍歷非遞歸算法是：
若2叉樹為空，則返回；否則，令p=T，p入隊；
⑴ 隊首元素出隊到p；
⑵訪問p所指向的結(jié)點；
⑶將p所指向的結(jié)點的左、右子結(jié)點順次入隊。直到隊空為止。
#define MAX_NODE 50
void LevelorderTraverse( BTNode *T)
{ BTNode *Queue[MAX_NODE] , *p=T ;
int front=0 , rear=0 ;
if (p!=NULL)
{ Queue[++rear]=p; /* 根結(jié)點入隊 */
while (front<rear)
{ p=Queue[++front]; visit( p->data );
if (p->Lchild!=NULL)
Queue[++rear]=p; /* 左結(jié)點入隊 */
if (p->Rchild!=NULL)
Queue[++rear]=p; /* 左結(jié)點入隊 */
}
}
}
“遍歷”是2叉樹最重要的基本操作，是各種其它操作的基礎(chǔ)，2叉樹的許多其它操作都可以通過遍歷來實現(xiàn)。如建立2叉樹的存儲結(jié)構(gòu)、求2叉樹的結(jié)點數(shù)、求2叉樹的深度等。
2叉樹的擴充方法是：在2叉樹中結(jié)點的每個空鏈域處增加1個擴充的結(jié)點(總是葉子結(jié)點，用方框“□”表示)。對2叉樹的結(jié)點值：
◆ 是char類型：擴充結(jié)點值為“？”或“#”；
◆ 是int類型：擴充結(jié)點值為0或⑴；
下面的算法是2叉樹的前序創(chuàng)建的遞歸算法，讀入1棵2叉樹對應的擴充2叉樹的前序遍歷的結(jié)點值序列。每讀入1個結(jié)點值就進行分析：
◆ 若是擴充結(jié)點值：令根指針為NULL；
◆ 若是(正常)結(jié)點值：動態(tài)地為該指針分配1個結(jié)點，將該值賦給根結(jié)點，然后遞歸地創(chuàng)建根的左子樹和右子樹。
算法實現(xiàn)：
#define NULLKY ‘?’
#define MAX_NODE 50
typedef struct BTNode
{ char data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ;
BTNode *Preorder_Create_BTree(BTNode *T)
/* 建立鏈式2叉樹，返回指向根結(jié)點的指針變量 */
{ char ch ;
ch=getchar() ;
if (ch==NULLKY)
{ T=NULL; return(T) ; }
else
{
T=(BTNode *)malloc(sizeof(BTNode)) ;
T
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學習，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
