擁抱「資料結構」的「演算法」(09) - 樹 Tree
前言
前面幾天都在講線性資料結構，現在開始要來講非線性的資料結構了，今天就先從樹狀結構講起
生活常識
最近假日的風景區常常爆滿，大家都到戶外踏青去了，爬爬山，走走路，欣賞大自然的風景，熱了就道樹下乘涼，而你有注意過樹為什麼可以長得如此茂密或高大嗎？樹的主要由根、莖、葉、花、果實、種子組成，各個部位都會隨著時間與氣候的變化而生長，我們快速地從一棵樹的狀態判斷出它的生長情況，例如分支多不多，樹葉多不多
圖片來源:https://www.pexels.com/zh-tw/photo/9277/
另外，我們也會用枝繁葉茂來形容家族人丁興旺的樣子，如以下的組織圖
最後就是我們常見的資料夾了，其實也是一層一層的進行儲存與管理
專業知識 - 樹 Tree
透過上述的生活例子，會發現樹狀結構是一種階層式的架構，而非線性結構，資料已經沒有前後的關係，只有上對下，或下對上的關係，像是爸爸與小孩之間的關係
樹的定義
是由一個或多個節點所組成的集合
- 有一個特定節點，稱為根節點(Root)，會畫在最頂層(現實生活中的樹根是在最底層)，樹不可為空
- 除了根節點之外，其他的節點為互斥的集合，每個集合是樹根節點的子樹(Subtree)
- 不會有迴路
專有名詞
樹根或根節點(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)，榨汁機入口先放入草莓，那麼殘渣的出口就會先看到草莓，所以草莓的殘渣會在最底部
留言
張貼留言