前言

前面幾天都在講線性資料結構，現在開始要來講非線性的資料結構了，今天就先從樹狀結構講起

生活常識

最近假日的風景區常常爆滿，大家都到戶外踏青去了，爬爬山，走走路，欣賞大自然的風景，熱了就道樹下乘涼，而你有注意過樹為什麼可以長得如此茂密或高大嗎？樹的主要由根、莖、葉、花、果實、種子組成，各個部位都會隨著時間與氣候的變化而生長，我們快速地從一棵樹的狀態判斷出它的生長情況，例如分支多不多，樹葉多不多

圖片來源:https://www.pexels.com/zh-tw/photo/9277/

另外，我們也會用枝繁葉茂來形容家族人丁興旺的樣子，如以下的組織圖

最後就是我們常見的資料夾了，其實也是一層一層的進行儲存與管理

專業知識 - 樹 Tree

透過上述的生活例子，會發現樹狀結構是一種階層式的架構，而非線性結構，資料已經沒有前後的關係，只有上對下，或下對上的關係，像是爸爸與小孩之間的關係

樹的定義

是由一個或多個節點所組成的集合

1. 有一個特定節點，稱為根節點(Root)，會畫在最頂層(現實生活中的樹根是在最底層)，樹不可為空
2. 除了根節點之外，其他的節點為互斥的集合，每個集合是樹根節點的子樹(Subtree)
3. 不會有迴路

專有名詞

• 樹根或根節點(Root)
  沒有父節點，會畫在樹狀結構的最頂層，例如：Alice

• 父節點(Parent)
  如果此節點有下層節點，則為父節點，例如：Alice、Bob、Chris
  Alice 下面有 Bob 跟 Chris
  Bob 下面有 Eva 跟 Frank
  Chris 下面有 Gina

• 子節點(Children)
  如果此節點有上層節點，則為子節點，例如：Bob、Chris、David、Eva、Frank、Gina
  Bob、Chris、David 上面有 Alice
  Eva、Frank 上面有 Bob
  Gina 上面有Chris

• 兄弟節點(Siblings)
  有共同的父節點，例如：Bob、Chris、David 與 Eva、Frank
  Bob、Chris、David 共同的父節點為 Alice
  Eva、Frank 共同的父節點為 Bob

• 分支度(Degree)
  父節點下有幾個子節點，例如：
  Alice 分支度是 3，有 3 個子節點(Bob、Chris、David)
  Bob 分支度是 2，有 2 個子節點(Eva、Frank)

• 終端節點或樹葉節點(Terminal)
  沒有子節點(下層節點)，例如：David、Eva、Frank、Gina

• 非終端節點(Non-terminal)
  除了樹葉節點之外，其他都是非終端節點，例如：Alice、Bob、Chris

• 階層(Level)
  位於樹狀結構的第幾層，例如：
  Alice 在第 1 層
  Frank 在第 3 層

• 高度(Height)或深度(Depth)
  樹狀結構總共有幾層，例如：以Alice的樹狀圖來說，高度為 3

今日小結

樹狀結構有比較多的專有名詞，雖然對這些名詞感到陌生，但其實並不會很難，跟我們常見的組織圖或是親屬關係有很多相似的地方，這些基本的觀念要理解清楚，會有助於了解明天二元樹的內容哦！

今日謎題

文字家族要舉辦中秋節聚餐，要推派幾個人出來負責籌辦，只要符合以下任一條件者就是籌辦人員：

• 家族第 2 代，且生了 2 個小孩
• 沒有生過小孩的人

你知道籌辦成員有哪些人嗎？是哪些文字嗎？這些文字之間似乎暗藏著某些訊息，好像可以組成某一個字，你發現了嗎？

昨日解謎

謎題說明：要掌握先進先出的特性(FIFO)，榨汁機入口先放入草莓，那麼殘渣的出口就會先看到草莓，所以草莓的殘渣會在最底部