Review

今天要講的資料結構是Tree，在Day10介紹Spanning tree，已經有簡略過Tree的定義了。

樹 Tree

沒有環路的連通圖

• Tree是一種類似現實生活中樹幹和樹枝的非線性資料結構
• 在CS中，我們通常將樹畫成顛倒的，樹根在上面，樹葉在下面
• 非線性，且階層式的方式儲存資料
• ex: 比賽賽程、公司職位圖、家族族譜

樹的構成

1. 有根樹 Rooted tree : 在資料結構中的樹稱為Rooted tree。
2. 樹根 Root : 樹中會有一個特別的節點為root，root通常畫在樹的最上面。
3. 子樹 Subtree : Root會包含0個或多個subtree，通常畫在root的下面。

以上圖(祖譜)為例子，整個祖譜就是rooted tree，而祖父就是root，此root包含3個subtree，分別是以父母為root和姑姑姑丈為root及叔叔阿姨為root的subtree。
在從父母為root的subtree往下看，又分為兒子和女兒兩個subtree。

• 由此可以知道，Rooted tree 就是從 root 一直遞迴下去，直到沒有subtree的節點。

樹狀結構 (示意圖)

名詞

• 樹的節點分成兩類:
  1. 內部節點 internal node : 有Subtree的節點。又可以說是non-terminal node 或 branch。
     ex : 圖中的A點、B點、C點、D點、F點都有Subtree。
  2. 外部節點 external node : 沒有Subtree的節點。又可以說是terminal node 或是 leaf。
     ex : 圖中的E點、G點、H點、I點都沒有Subtree。
• 節點的關係
  1. 父節點 parent node : parent node 在 child node的上面。
     ex : 圖中的A點是B點、C點的parent node。
  2. 子節點 child node : child node 在 parent node的下面。
     ex : 圖中的B點、C點是A點的child node。
  3. 兄弟節點 siblings : 擁有同一個 parent node 的節點。
     ex : 圖中的B點、C點是 siblings。
• 階度 Level
  • 第1階 : Root
  • 第2階 : Root的child node。
  • 第3階 : Root的child node的child node。
  • .....以此類推。
• 高度 Height : tree 的最大 level。
  ex : 上圖的樹的height = 4 。
• 森林 Forest : 一個圖形裡有兩棵或兩顆以上的tree。

參考

細談資料結構 第六版
ISBN 978-986-312-014-8

林明進老師：「可以成為一顆大樹，就不要只作一片葉子。」