iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 9
0
Software Development

擁抱「資料結構」的「演算法」系列 第 9

擁抱「資料結構」的「演算法」(09) - 樹 Tree

前言

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


生活常識

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

https://ithelp.ithome.com.tw/upload/images/20200923/20129841BXV5fWxA3G.png
圖片來源:https://www.pexels.com/zh-tw/photo/9277/

另外,我們也會用枝繁葉茂來形容家族人丁興旺的樣子,如以下的組織圖
https://ithelp.ithome.com.tw/upload/images/20200923/201298410s6Qn5bMVO.png

最後就是我們常見的資料夾了,其實也是一層一層的進行儲存與管理
https://ithelp.ithome.com.tw/upload/images/20201014/20129841b09ll1P2JV.png


專業知識 - 樹 Tree

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

樹的定義

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

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

專有名詞

https://ithelp.ithome.com.tw/upload/images/20200923/20129841qVrB4NbUWa.png

  • 樹根或根節點(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 個小孩
  • 沒有生過小孩的人

https://ithelp.ithome.com.tw/upload/images/20200923/20129841IjhPv5WwLb.png

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

昨日解謎

謎題說明:要掌握先進先出的特性(FIFO),榨汁機入口先放入草莓,那麼殘渣的出口就會先看到草莓,所以草莓的殘渣會在最底部
https://ithelp.ithome.com.tw/upload/images/20200923/20129841A2BjLjdM2R.png


上一篇
擁抱「資料結構」的「演算法」(08) - 佇列 Queue
下一篇
擁抱「資料結構」的「演算法」(10) - 二元樹 Binary Tree
系列文
擁抱「資料結構」的「演算法」30

尚未有邦友留言

立即登入留言