廢話時間

半夜心血來潮跟好兄弟寫了半首歌，早上還是要起來更新鐵人賽ㄉ我，還是可以被稱讚ㄅ

前言

今天進入到新的章節，我們要談的是樹，在進入樹之前，要先提即樹的各種相關術語，這樣一來，未來進入二元樹、引線二元樹、Heap，甚至高等樹的AVL Tree、B Tree of order m，才有辦法以通用的語言來理解這些資料結構！

Tree 的相關術語

樹必須由 ≥1 個 node 所組成 (不可為空)，在此圖我將每個 node 都進行了編號，後面講解起來會較於便利

• Node's degree : 對於 Node 1 而言 Degree = 3，對於 Node 4 而言 Degree = 2
• Tree's degree : 挑所有 Node 中的最高 Degree，所以在此圖中 Degree = 3

而子點父點、以及 sibling 均有在圖中說明囉

Tree 的表示方法

利用 LinkedList 建置

Node 的結構會根據 Tree's Degree 去決定要建立多少個 link
設要使用的 Tree's Degree = m，且具有 n 個 node
代表可用連結僅只有 n-1 條
那總共會浪費 m*n-(n-1) 條連結，非常浪費空間！

轉化成 Binary Tree 表示

1. 先將兄弟建立連結
2. 保留最左的父親連結、刪除其他父子連結
3. 將水平的連結往右下轉 45 度

child-sibling

子點利用左側連結，兄弟利用右側連結