以往線性表我都是先講建立再講遍歷，但樹結構的建立其實比遍歷更困難些，因此我們先來講遍歷吧!
已知樹每個節點長這樣:
typedef struct TNode * Position; //把節點指針稱為Position
typedef Position BinTree; //把根的指針稱為BinTree，其實這兩個相同
struct TNode{
ElementType Data;
BinTree Left; //左子樹
BinTree Right; //右子樹
};
一樣，我們先來定義樹有哪些方法，對於一棵二叉樹(BT)，一般來說會有以下方法:
1. bool isEmpty(Bintree BT) 樹是否為空，如果BT為空回傳True，否則False
2. void TravelTree(BinTree BT) 遍歷樹，也是本章節要講的重點
3. BinTree CreateBinTree() 建立樹，留到下一章節一、遍歷二叉樹
以往線性表，從起點到終點全部連在一條線上，現在樹則是有了分岔，到底樹結構要怎麼遍歷呢? 樹的遍歷分為以下四種主流
先序、中序、後序、層序 ，差別在訪問時間點
1. 中序:
中序的意思是我先遍歷左子樹後、訪問節點、然後訪問右子樹，遍歷過程可以總結為以下幾點:
(1) 中序遍歷其左子樹
(2) 遍歷根節點
(3) 中序遍歷其右子樹
中序輸出: D B E F A G H C I
其實我們從頭到尾都是在執行上面那三個步驟，因此我們可以將過程寫成遞歸模式void InorderTravel(BinTree BT){
if(BT){ //如果 BT!=NULL
InorderTravel(BT->Left); //先遍歷左節點 (如果有左節點的話)
printf("%d",BT->Data); //訪問子樹根節點
InorderTravel(BT->Right); //訪問完後遍歷右節點
}
}輸出: D B E F A G H C I
雖然短短三行，不過比較抽象，建議自己用手畫一次，自己腦內遍歷一次會比較清楚喔。
2. 先序
前序與中序之間的差別在於，遍歷根結點的時間點不同，先序之所以為"先"，就是因為先遍歷了結點
(1) 遍歷根節點
(2) 先序遍歷其左子樹
(3) 先序遍歷其右子樹void PreorderTravel(BinTree BT){
if(BT){ //如果 BT!=NULL
printf("%d",BT->Data); //訪問子樹根節點
PreorderTravel(BT->Left); //先遍歷左節點 (如果有左節點的話)
PreorderTravel(BT->Right); //訪問完後遍歷右節點
}
}輸出結果 : A B D F E C G H I
仔細觀察的話可以知道，先序就是遇到什麼就輸出什麼!!
3. 後序
一模一樣阿，真的就只是差在輸出節點的時間點不同罷了!
(1) 中序遍歷其左子樹
(2) 中序遍歷其右子樹
(3) 遍歷根節點void PostorderTravel(BinTree BT){
if(BT){ //如果 BT!=NULL
PostorderTravel(BT->Left); //先遍歷左節點 (如果有左節點的話)
PostorderTravel(BT->Right); //訪問完後遍歷右節點
printf("%d",BT->Data); //訪問子樹根節點
}
}輸出結果 : D E F B H G I C A
4. 三個序的總結
前、中、後序必考，大家一定要記清楚啊，這代碼必須看懂 !! 此外，前中後序也可以畫作一張圖。
紅、黃、藍，分別為前中後序遇到時會輸出的時間點，綠色線則是遍歷時固定路徑，可以看到前序的輸出點在節點左上角，遇到即輸出 ; 中序在節點下方，代表線在遍歷完左節點時才會遍歷節點 ; 後序在節點右方代表線在遍歷完右節點後才會遍歷節點。
依照這樣的思想，先序遍歷即輸出，中序遍歷第一遍時先不輸出，第二遍輸出，後序則是遍歷一、二遍時不輸出，第三遍才輸出。依照所有的遞歸函數都可以用Stack來做的思想，我們也能寫出遍歷的非遞歸方法了 !
中序的非遞歸遍歷方法，已經知道中序是遍歷第二遍才輸出，因此我們要做的工作是找到哪些節點遍歷兩遍了。(使用Stack)void InorderTravel(BinTree BT){
Bintreee T = BT; //從根結點出發
Stack s = createStack() //建立一個Stack
while(T || !isEmpty(s)){ //結束條件 T==null && s為空了
while(T) { //T將左邊所有節點押入直到T==null
Push(S,T);
T = T->Left;
}
T = Pop(S); //當T==null，pop最上層的節點指針給T
printf("%d",T->Data); //輸出
T = T->Right;
//T 進入右節點，重複押入所有左節點動作，要是右==null，不執行while(T)，再次pop
}
}
輸出: D B E F A G H C I
稍微複雜了點，但仔細研究後發現還蠻有趣的。
5. 層序
然額，有時候我們會希望是一層一層的遍歷，因此有了層序。由於是一層一層遍歷，下一層需要先"等"上一層執行完畢，看到"等"這個字，是不是就想到了Queue了 !!
層序是下三個動作不斷重複
(1) 從Queue取出一個節點
(2) 訪問該節點
(3) 如果該節點左右有子，將其左右子順序入Queue層序代碼:
void LevelorderTravel(BinTree BT){
Queue Q = createQueue(); //建立Queue
BinTree T ;
if(!BT) return; //如果BT是空樹，直接返回
Add(Q,BT); //先把頭節點入隊
while(!isEmpty(Q)){
T = DeleteQ(Q); //步驟1
printf("%d",T->Data); //步驟2
if(T->Left) Add(Q,T->Left);
if(T->Right) Add(Q,T->Right); //步驟3
}
}
輸出結果 : A B C D F G I E H二、建立二叉樹
由於二叉樹並非線性結構，建立時必須確保有中結點，常見的建立方法是層序建立，這種建立方法能確保擁有節點的才會有子節點。
以上面的圖為例，空的節點設為0，那麼建立的順序就是 :
A B C D F G I 0 0 E 0 0 H 0 0 0 0 0 0 
創建過程如下:
1. 輸入第一個數，如果不為0，分配節點單位，將該節點指針放入Queue
2. 如果Queue不為空，從Queue中取出一個節點，並建立該節點孩子
3-1. 讀入下一個數，如果為0，將左節點指針為空，有，則將數放入節點，將其設為出隊節
點的左孩子，同時將這個子節點放入Queue
3-2. 再讀下一個數，如果為0，將右節點指針為空，有，則將數放入節點，將其設為出隊節
點的右孩子，同時將這個子節點放入Queue
4. 重複 2、3的動作，直到Queue為空
/****設0代沒有節點******/
typedef int ElementType;
#define NoNode 0BinTree CreateBinTree(ElementType arr[]){
ElementType Data;
BinTree BT, T; //BT要設為根節點，Temp則是要接收Queue吐的值
Queue Q = createQueue();
//建立根節點
if(arr[0]!= NoNode){
BT = (BinTree)malloc(sizeof(struct TNode));
BT->Data = arr[0];
BT->Left = BT->Right = NULL;
Add(Q,BT);
}else return NULL; //如果是空節點，返回NULL
int i=1; //arr下標
while(!isEmpty(Q)){
T = DeleteQ(Q);
Data = arr[i++]; //讀入左孩子的值，讀完後i+1
if(Data == NoNode) T->Left = NULL; //要是下個值為0，左節點設為空
else{ //建立新的左子節點
T->Left = (BinTree)malloc(sizeof(struct TNode));
T->Left->Data = Data;
T->Left->Left = T->Left->Right = NULL ; //左子節點有子節點
AddQ(Q,T->Left); //入隊
}
Data = arr[i++];
if(Data == NoNode) T->Right = NULL;
else{
T->Right = (BinTree)malloc(sizeof(struct TNode));
T->Right->Data = Data;
T->Right->Left = T->Right->Right = NULL ;
Add(Q,T->Right);
}
} //結束while
return BT;
}
完整程式碼 :
輸出結果 :
參考資料:
- 《数据结构》（第2版），陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2016年6月
- https://www.icourse163.org/course/ZJU-93001
