0. 寫在最前面
本文轉載位址：二叉樹前序周遊、中序周遊、後序周遊、層序周遊的直覺了解 - 白夜行的狼的部落格
複習到二叉樹，看到網上諸多部落格文章各種繞，記得頭暈。個人覺得數學、算法這些東西都是可以更直覺簡潔地表示，然後被記住的，并不需要靠死記硬背。
本文的程式基本來源于《大話資料結構》，個人感覺是一本非常好的書，推薦去看。
1. 為什麼叫前序、後序、中序
一棵二叉樹由根結點、左子樹和右子樹三部分組成，若規定 D、L、R 分别代表周遊根結點、周遊左子樹、周遊右子樹，則二叉樹的周遊方式有 6 種：DLR、DRL、LDR、LRD、RDL、RLD。由于先周遊左子樹和先周遊右子樹在算法設計上沒有本質差別，是以，隻有三種方式：
- DLR–前序周遊（根在前，從左往右，一棵樹的根永遠在左子樹前面，左子樹又永遠在右子樹前面 ）
- LDR–中序周遊（根在中，從左往右，一棵樹的左子樹永遠在根前面，根永遠在右子樹前面）
- LRD–後序周遊（根在後，從左往右，一棵樹的左子樹永遠在右子樹前面，右子樹永遠在根前面）
2. 需要注意幾點
- 根是相對的，對于整棵樹而言隻有一個根，但對于每棵子樹而言，又有自己的根。比如對于下面三個圖，對于整棵樹而言，A是根，A分别在最前面、中間、後面被周遊到。而對于D，它是G和H的根，對于D、G、H這棵小樹而言，順序分别是DGH、GDH、GHD；對于C，它是E和F的根，三種排序的順序分别為： CEF、ECF、EFC。是不是根上面的DLR、LDR、LRD一模一樣呢～～
- 整棵樹的起點，就如上面所說的，從A開始，前序周遊的話，一棵樹的根永遠在左子樹前面，左子樹又永遠在右子樹前面，你就找他的起點好了。
- 二叉樹結點的先根序列、中根序列和後根序列中，所有葉子結點的先後順序一樣
- 建議看看文末第3個參考有趣詳細的推導
| 前序周遊（DLR） | 中序周遊（LDR） | 後序周遊（LRD） |
|---|---|---|
 |  | |
3. 算法上的前中後序實作
除了下面的遞歸實作，還有一種使用棧的非遞歸實作。因為遞歸實作比較簡單，且容易關聯到前中後，是以
typedef struct TreeNode
{
int data;
TreeNode * left;
TreeNode * right;
TreeNode * parent;
}TreeNode;
void pre_order(TreeNode * Node)//前序周遊遞歸算法
{
if(Node == NULL)
return;
printf("%d ", Node->data);//顯示節點資料，可以更改為其他操作。在前面
pre_order(Node->left);
pre_order(Node->right);
}
void middle_order(TreeNode *Node)//中序周遊遞歸算法
{
if(Node == NULL)
return;
middle_order(Node->left);
printf("%d ", Node->data);//在中間
middle_order(Node->right);
}
void post_order(TreeNode *Node)//後序周遊遞歸算法
{
if(Node == NULL)
return;
post_order(Node->left);
post_order(Node->right);
printf("%d ", Node->data);//在最後
}
4. 層序周遊
層序周遊嘛，就是按層，從上到下，從左到右周遊，這個沒啥好說的。
參考
《大話資料結構》書籍
二叉樹的周遊DLR LDR LRD - 陳斌彬的技術部落格
看懂二叉樹的三種周遊_soundwave_的部落格-CSDN部落格_二叉樹周遊