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