資料結構：樹與二叉樹核心概念、性質與轉換
樹的定義與基本術語
樹 = n (n≥0) 節點有限集。n=0 為空樹。非空樹：唯一根節點；其餘節點分為 m 個不相交子樹，各子樹本身也是樹 (遞歸定義)。
| 術語 | 定義 |
|---|
| 節點度 | 子樹棵數 |
| 樹的度 | 所有節點度的最大值 |
| 葉子/終端節點 | 度為 0 |
| 分支/非終端節點 | 度 ≠ 0 (根除外稱內部節點) |
| 層次 | 根為第 1 層，子節點 = 父層次 + 1 |
| 深度/高度 | 最大層次值 |
| 有序/無序樹 | 子樹有無左右順序之分 |
| 森林 | m 棵互不相交樹的集合 (刪除根後形成) |
二叉樹定義與特殊形態
二叉樹 = n 節點有限集。空樹或：唯一根 + 左/右子樹 (互不相交，皆為二叉樹)。特徵：度 ≤ 2、左右有序不可顛倒、單子樹也分左右。
- 滿二叉樹：所有分支節點度=2，葉子僅在最底層，同深度下節點數最多
- 完全二叉樹：按層序編號與同深度滿二叉樹位置對應。葉子僅最底兩層、最底層葉子靠左、倒數第二層葉子靠右、度=1 僅有左孩子、同節點數深度最小
二叉樹五大性質 (含證明)
- 第 i 層至多 2^(i-1) 節點 (數學歸納法)
- 深度 k 樹至多 2^k - 1 節點 (各層上限求和)
- n0 = n2 + 1 (葉子數 = 度為 2 節點數 + 1)。證明：N=n0+n1+n2，分支數 B=n1+2n2，N=B+1 → 推導得證
- n 節點完全二叉樹深度 = ⌊log2 n⌋ + 1
- 完全二叉樹編號規則：i=1 為根；i>1 雙親 = ⌊i/2⌋；2i>n 為葉子無左孩子，否則左孩子=2i；2i+1>n 無右孩子，否則右孩子=2i+1
儲存結構
- 順序儲存：適合完全二叉樹，陣列下標對應編號
- 鏈式儲存：二叉鏈表 (左/右指標)、三叉鏈表 (+父指標)
遍歷與線索化
- 三種遞歸遍歷：先序/中序/後序
- 非遞歸：堆疊 (先/中序)、雙堆疊+標記 (後序)、隊列 (層次)
- 線索二叉樹：利用 n+1 個空指標域存前驅/後繼，中序線索化遞歸算法、無堆疊遍歷
樹、森林與二叉樹轉換
- 樹 → 二叉樹：長子作為左孩子，兄弟作為右孩子 (左孩子-右兄弟表示法)
- 森林 → 二叉樹：各樹轉二叉樹，首樹根為整體根，其餘樹根串聯為右孩子鏈
- 二叉樹 → 樹：刪除所有右孩子連線，層次還原
哈夫曼樹 (最優樹)
帶權路徑長度 (WPL) 最小的二叉樹。構造：反覆合併權值最小的兩棵樹。應用：哈夫曼編碼 (最佳前綴碼)、最優合併模式。
