1 遞歸算法
算法的遞歸定義是：
若二叉樹為空，則遍歷結束；否則
⑴ 中序遍歷左子樹(遞歸調用本算法)；
⑵ 訪問根結點；
⑶ 中序遍歷右子樹(遞歸調用本算法)。
中序遍歷的遞歸算法
void InorderTraverse(BTNode *T)
{ if (T==NULL)
return；
InorderTraverse(T->Lchild) ;
visit(T->data) ; /* 訪問根結點 */
InorderTraverse(T->Rchild) ;
} 2 非遞歸算法（略）
設T是指向二叉樹根結點的指針變量，非遞歸算法是：
若二叉樹為空，則返回；否則，令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!\n”) ;
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 遞歸算法
算法的遞歸定義是：
若二叉樹為空，則遍歷結束；否則
⑴ 後序遍歷左子樹(遞歸調用本算法)；
⑵ 後序遍歷右子樹(遞歸調用本算法) ；
⑶ 訪問根結點 。
後序遍歷的遞歸算法
void PostorderTraverse(BTNode *T)
{ if (T!=NULL)
{ PostorderTraverse(T->Lchild) ;
PostorderTraverse(T->Rchild) ;
visit(T->data) ; /* 訪問根結點 */
}
}
遍歷二叉樹的算法中基本操作是訪問結點，因此，無論是哪種次序的遍歷，對有n個結點的二叉樹，其時間復雜度均為O(n) 。
2 非遞歸算法（略）
在後序遍歷中，根結點是最後被訪問的。因此，在遍歷過程中，當搜索指針指向某一根結點時，不能立即訪問，而要先遍歷其左子樹，此時根結點進棧。當其左子樹遍歷完後再搜索到該根結點時，還是不能訪問，還需遍歷其右子樹。所以，此根結點還需再次進棧，當其右子樹遍歷完後再退棧到到該根結點時，才能被訪問。
因此，設立一個狀態標志變量tag ：
其次，設兩個堆棧S1、S2 ，S1保存結點，S2保存結點的狀態標志變量tag 。S1和S2共用一個棧頂指針。
設T是指向根結點的指針變量，非遞歸算法是：
若二叉樹為空，則返回；否則，令p=T；
⑴ 第一次經過根結點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!\n”) ;
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) ;
}}
層次遍歷二叉樹，是從根結點開始遍歷，按層次次序“自上而下，從左至右”訪問樹中的各結點。 為保證是按層次遍歷，必須設置一個隊列。 設T是指向根結點的指針變量，層次遍歷非遞歸算法是：
若二叉樹為空，則返回；否則，令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; /* 左結點入隊 */
}
}
}
“遍歷”是二叉樹最重要的基本操作，是各種其它操作的基礎，二叉樹的許多其它操作都可以通過遍歷來實現。如建立二叉樹的存儲結構、求二叉樹的結點數、求二叉樹的深度等。
二叉樹的擴充方法是：在二叉樹中結點的每一個空鏈域處增加一個擴充的結點(總是葉子結點，用方框“□”表示)。對於二叉樹的結點值：
◆ 是char類型：擴充結點值為“？”或“#”；
◆ 是int類型：擴充結點值為0或-1；
下面的算法是二叉樹的前序創建的遞歸算法，讀入一棵二叉樹對應的擴充二叉樹的前序遍歷的結點值序列。每讀入一個結點值就進行分析：
◆ 若是擴充結點值：令根指針為NULL；
◆ 若是(正常)結點值：動態地為該指針分配一個結點，將該值賦給根結點，然後遞歸地創建根的左子樹和右子樹。
算法實現：
#define NULLKY ‘?’
#define MAX_NODE 50
typedef struct BTNode
{ char data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ;
BTNode *Preorder_Create_BTree(BTNode *T)
/* 建立鏈式二叉樹，返回指向根結點的指針變量 */
{ char ch ;
ch=getchar() ;
if (ch==NULLKY)
{ T=NULL; return(T) ; }
else
{
T=(BTNode *)malloc(sizeof(BTNode)) ;
T–>data=ch ;
Preorder_Create_BTree(T->Lchild) ;
Preorder_Create_BTree(T->Rchild) ;
}
}
2 求二叉樹的葉子結點數
可以直接利用先序遍歷二叉樹算法求二叉樹的葉子結點數。只要將先序遍歷二叉樹算法中vist()函數簡單地進行修改就可以。
算法實現：
＃define MAX_STACK_SIZE 50
int BiTreeleaves( BTNode *T)
{ BTNode *stack[MAX_STACK_SIZE] ,*p=T;
int top=0, num=0;
if (T!=NULL)
{ stack[++top]=p ;
while (top>0)
{ p=stack[top--] ;
if (p->Lchild==NULL&&p->Rchild==NULL) num++ ;
if (p->Rchild!=NULL )
stack[++top]=p->Rchild;
if (p->Lchild!=NULL )
stack[++top]=p->Lchild;
}
}
return(num) ;
}
3 求二叉樹的深度
利用層次遍歷算法可以直接求得二叉樹的深度。
算法實現：
＃define MAX_NODE 50
int BiTreedepth( BTNode *T)
{ BTNode * Queue[MAX_NODE] ,*p=T;
int front=0 , rear=0, depth=0, level ;
/* level總是指向訪問層的最後一個結點在隊列的位置 */
if (T!=NULL)
{ Queue[++rear]=p; /* 根結點入隊 */
level=rear ; /* 根是第1層的最後一個節點 */
while (front<rear)
{ p=Queue[++front];
if (p->Lchild!=NULL)
Queue[++rear]=p; /* 左結點入隊 */
if (p->Rchild!=NULL)
Queue[++rear]=p; /* 左結點入隊 */
if (front==level)
/* 正訪問的是當前層的最後一個結點 */
{ depth++ ; level=rear ; }
}
}
}
/* 初始條件: 二叉樹T存在。操作結果: 返回T的深度 */
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T) return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else j=0;
return i>j?i+1:j+1;
}
