對於一種數據結構而言，遍歷是常見操作。二叉樹是一種基本的數據結構，是一種每個節點的兒子數目都不多於2的樹。二叉樹的節點聲明如下：
typedef struct TreeNode *PtrToNode;
typedef struct TreeNode *BinTree;
struct TreeNode
{
int Data; //為簡單起見，不妨假設樹節點的元素為int型
BinTree Left;
BinTree Right;
};
二叉樹的遍歷主要有先序遍歷，中序遍歷，後序遍歷，層序遍歷四種方式，下面一一介紹。
1. 先序遍歷
在先序遍歷中，對節點的訪問工作是在它的左右兒子被訪問之前進行的。換言之，先序遍歷訪問節點的順序是根節點-左兒子-右兒子。由於樹可以通過遞歸來定義，所以樹的常見操作用遞歸實現常常是方便清晰的。遞歸實現的代碼如下：
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(“%d\n”, BT->Data); //對節點做些訪問比如打印
PreOrderTraversal(BT->Left); //訪問左兒子
PreOrderTraversal(BT->Right); //訪問右兒子
}
}
由遞歸代碼可以看出，該遞歸為尾遞歸（尾遞歸即遞歸形式在函數末尾或者說在函數即將返回前）。尾遞歸的遞歸調用需要用棧存儲調用的信息，當數據規模較大時容易越出棧空間。雖然現在大部分的編譯器能夠自動去除尾遞歸，但是即使如此，我們不妨自己去除。非遞歸先序遍歷算法基本思路：使用堆棧
a. 遇到一個節點，訪問它，然後把它壓棧，並去遍歷它的左子樹；
b. 當左子樹遍歷結束後，從棧頂彈出該節點並將其指向右兒子，繼續a步驟；
c. 當所有節點訪問完即最後訪問的樹節點為空且棧空時，停止。
實現代碼如下：
void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MAX_SIZE); //創建並初始化堆棧S
while(T || !IsEmpty(S))
{
while(T) //一直向左並將沿途節點訪問（打印）後壓入堆棧
{
printf("%d\n", T->Data);
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S); //節點彈出堆棧
T = T->Right; //轉向右子樹
}
}
}
2. 中序遍歷
中序遍歷的遍歷路徑與先序遍歷完全一樣。其實現的思路也與先序遍歷非常相似。其主要的不同點是訪問節點順序不同：中序遍歷是訪問完所有左兒子後再訪問根節點，最後訪問右兒子，即為左兒子-根節點-右兒子。
遞歸實現的代碼如下:
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d\n", BT->Data);
InOrderTraversal(BT->Right);
}
}
非遞歸實現代碼如下:
void InOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MaxSize); //創建並初始化堆棧S
while(T || !IsEmpty(S))
{
while(T) //一直向左並將沿途節點壓入堆棧
{
Push(S,T);
T = T->Left;
}
if(!IsEmpty(S))
{
T = Pop(S); //節點彈出堆棧
printf("%d\n", T->Data); //（訪問） 打印結點
T = T->Right; //轉向右子樹
}
}
}
3. 後序遍歷
後序遍歷與中序遍歷，先序遍歷的路徑也完全一樣。主要的不同點是後序遍歷訪問節點的順序是先訪問左兒子和右兒子，最後訪問節點，即左兒子-右兒子-根節點。
遞歸實現思路與中序遍歷和先序遍歷相似，代碼如下:
void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d\n", BT->Data);
}
}
後序遍歷的非遞歸實現
思路一：
對於一個節點而言，要實現訪問順序為左兒子-右兒子-根節點，可以利用後進先出的棧，在節點不為空的前提下，依次將根節點，右兒子，左兒子壓棧。故我們需要按照根節點-右兒子-左兒子的順序遍歷樹，而我們已經知道先序遍歷的順序是根節點-左兒子-右兒子，故只需將先序遍歷的左右調換並把訪問方式打印改為壓入另一個棧即可。最後一起打印棧中的元素。代碼如下：
void PostOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S1 = CreatStack(MAX_SIZE); //創建並初始化堆棧S1
Stack S2 = CreatStack(MAX_SIZE); //創建並初始化堆棧S2
while(T || !IsEmpty(S1))
{
while(T) //一直向右並將沿途節點訪問（壓入S2）後壓入堆棧S1
{
Push(S2, T);
Push(S1, T);
T = T->Right;
}
if (!IsEmpty(S1))
{
T = Pop(S1); //節點彈出堆棧
T = T->Left; //轉向左子樹
}
}
while(!IsEmpty(S2)) //訪問（打印）S2中元素
{
T = Pop(S2);
printf("%d\n", T->Data);
}
}
思路一的優點是由於利用了先序遍歷的思想，代碼較簡潔，思路較清晰。缺點是需要用一個棧來存儲樹的所有節點，空間占用較大。
思路二：
要訪問一個節點的條件上一個訪問的節點是右兒子。我們可以增加一個變量Prev來判斷當前節點Curr的上一個節點與它的關系來執行相應的操作。
• 若Prev為空(Curr節點是根節點)或者Prev是Curr的父節點，將Curr節點的左孩子和右孩子分別壓入棧；
• 若Prev是Curr的左兒子，則將Curr的右兒子壓入棧；
• 否則Prev是Curr的右兒子，訪問Curr;
代碼如下:
void PostOrderTraversal(BinTree BT)
{
if(BT == NULL)
return ;
Stack S = CreatStack(MAX_SIZE);
BinTree Prev = NULL , Curr = NULL; //初始化
s.push(BT);
while(!IsEmpty(S))
{
Curr = Top(S); //將棧頂元素賦給Curr
if(Prev == NULL || Prev->Left == Curr || Prev->Right == Curr) //若Prev為NULL或是Curr的父節點
{
if(Curr->Left != NULL)
Push(S, Curr->Left);
else if(Curr->Right != NULL)
Push(S, Curr->Right);
}
else if(Curr->Left == Prev) //若Prev是Curr的左兒子
{
if(Curr->Right != NULL)
Push(S, Curr->Right);
}
else
{
printf("%d\n", Curr->Data); //訪問當前節點
Pop(S); //訪問後彈出
}
Prev = Curr; //處理完當前節點後將Curr節點變為Prev節點
}
}
4. 層序遍歷
二叉樹遍歷的核心問題是二維結構的線性化。我們通過節點訪問其左右兒子時，存在的問題是訪問左兒子後，右兒子怎麼訪問。因此我們需要一個存儲結構保存暫時不訪問的節點。前面三種遍歷方式的非遞歸實現，我們是通過堆棧來保存。事實上也可以通過隊列來保存。
隊列實現的基本思路：遍歷從根節點開始，首先將根節點入隊，然後執行循環：節點出隊，訪問（訪問）根節點，將左兒子入隊，將右兒子入隊，直到隊列為空停止。
這種遍歷方式的結果是將二叉樹從上到下，從左至右一層一層的遍歷，即層序遍歷，代碼實現如下:
void LevelOrderTraversal(BinTree BT)
{
BinTree T;
Queue Q; //聲明一個隊列
if (BT == NULL)
return; //如果樹為空，直接返回
Q = CreatQueue(MAX_SIZE); //創建並初始化隊列
AddQ(Q, BT); //將根節點入隊
while (!IsEmpty(Q))
{
T = DeleteQ(Q); ��� //節點出隊
printf("%d\n", T->Data); //訪問出隊的節點
if (T->Left) AddQ(Q, T->Left); //若左兒子不為空，將其入隊
if (T->Right) AddQ(Q, T->Right) //若右兒子不為空，將其入隊
}
}
理解上述四種二叉樹遍歷方式後，不妨來小試牛刀：List Leaves, Tree Traversals Again.
二叉樹遍歷（圖解） http://www.linuxidc.com/Linux/2015-07/119765.htm
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
