【複習整理】基礎資料結構（C語言）：二元樹（Binary tree）
本系列的文章，主要是讓自己快速複習資料結構。由於多年前在學校學的資料結構實作已印象模糊，腦海中只剩下相關的概念（唉~久沒複習蠻容易還給老師的），因此透過在網路上觀摩別人的教學或閱讀書籍，然後練習與整理成文章，達到快速複習的目標。
參考的教學如下：《動畫圖解資料結構（第二版）》，作者：李春雄C 語言學習筆記 : 二元樹
http://yhhuang1966.blogspot.com/2018/06/c.html?m=1[軟體工程師雜談] 輕鬆搞懂資料結構: 樹(Tree)
https://youtu.be/xDwFMffqLbw
下面開始複習二元樹（Binary tree）：
在開始複習二元樹之前，先來回顧樹狀結構，而樹（Tree）的應用例子有祖譜與政府組織圖等。
樹（Tree）是由一個（含）以上的節點所組成的有限集合，其至少有一個根節點（Root node），若有根節點以外的節點，可分成一個（含）以上的互斥集合，即為根節點的子樹（Subtree）。樹可視為圖（Graph）的一種特例，即為一種無迴路（Loopless）的無向圖形（Undirected Graph）。下圖是一個高度為3的樹。
樹的相關名詞解釋：
● 節點（Node）：一筆資料即為一個節點，如上圖的A~F皆為節點。
● 父節點（Parent）：節點的上一個節點，即為該節點的父節點，如上圖的A為B~D的父節點。
● 子節點（Children）：節點的下一個節點，即為該節點的子節點，如上圖的B~D皆為A的子節點。
● 根節點（Root node）：樹的最上層節點（無父節點者），如上圖的A即為根節點。
● 葉節點（Leaf node）：無子節點的節點，，即為葉節點，又稱為終端節點（Terminal node），如上圖的E~F皆為葉節點。
● 子樹（Subtree）：節點以下並且相連的樹狀結構，即為該節點的子樹，如上圖的D–G為A的子樹。
● 樹林（Forest）：除去根節點後，其互不相連的各樹狀結構，即為樹林。
● 階度（Level）：節點在樹狀結構的階層位置，根節點的階度為 1。
● 高度（Height）：樹的最大階度即為樹的高度。
● 分支度（Degree）：節點擁有的子樹個數稱為該節點的分支度，上圖根節點的分支度為3。
二元樹（Binary tree）則為每個節點皆符合 0 ≤ 分支度 ≤ 2，並且有左、右子樹之分的樹。其可進一步分為下列幾種二元樹：
- 斜曲二元樹（Skewed Binary tree）：
如下圖所示，只有左節點的樹為左斜曲二元樹（Left-skewed Binary tree），只有右節點的樹為右斜曲二元樹（Right-skewed Binary tree）。
- 嚴格二元樹（Strictly Binary tree）：
每個非葉節點皆有非空的左右節點之二元樹（如下圖所示）。
- 完滿二元樹（Full Binary tree）：
高度h（高度h ≥ 0）且具有(2^h) -1個節點的二元樹（如下圖所示）。
- 完整二元樹（Full Binary tree）：
滿足下列條件（若且為若）的二元樹：
◎ (2^(h-1))-1 ≤ n ≤ (2^h)-1，其中n為節點總數、h為高度。
◎ 節點編號會跟高度h之完滿二元樹的前n個節點編號一致。
由上述可以推知，「完滿二元樹」≥「完整二元樹」≥「嚴格二元樹」，因此完滿二元樹必為完整二元樹，但完整二元樹不一定是完滿二元樹。
二元樹基本上有兩種表示法：
- 陣列（Array）表示法：
如下圖所示，將高度h的二元樹視作完滿二元樹，接著規劃大小為(2^h)-1的陣列，最後依照順序將節點編號存入陣列。
- 鏈結串列（Linked list）表示法：
如下圖所示，鏈結串列的節點結構包含左右兩個分別指向左右子樹的指標（LChild與RChild），以及中間儲存資料的空間。接著採用此節點結構用來表示二元樹。
二元樹的走訪有三種，分別為前序追蹤（Pre-order）、中序追蹤（In-order）與後序追蹤（Post-order）。
- 前序追蹤（Pre-order）：又稱為「深度優先搜尋（Depth-First-Search，DFS）」，其追蹤順序為樹根→左子樹→右子樹，即為從父節點開始走訪，接著往左子樹走，直到無法前進後，接續處理右子樹。
- 中序追蹤（In-order）：又稱為「對稱追蹤」，其追蹤順序為左子樹→樹根→右子樹，即先往左子樹方向到無法前進，再退回父節點，接著再走訪右子樹。
- 後序追蹤（Post-order）：又稱為「廣度優先搜尋（Breadth-First-Search，BFS）」，其左子樹→右子樹→樹根，即先往左子樹方向到無法前進，再往右子樹方向到無法前進，接著才退回父節點。
對照下圖與上述三種追蹤，該二元數的前序追蹤的順序為8→7→4→2→10→16→11，中序追蹤的順序則為4→7→2→8→16→10→11，後序追蹤的順序則為4→2→7→16→11→10→8。
