tree

tree

「樹」。樹是一種很特別的圖。樹的定義是:任兩點之間都相通,並且沒有「環」的圖。「環」是指繞圈子的循環路線。

樹的定義對初學者來說或許太過抽象。換個說法吧:一棵樹可想做是由一個點開始,藉由許多條邊不斷地延伸拓展到其他點,而且點和邊都不會重複地被拓展到。

node

「節點」。進行延伸拓展的點、被延伸拓展到的點,稱作「節點」,也就是說樹上的點都是「節點」。

【註:為了方便,以下仍稱呼「點」。】

branch

「枝」。延伸拓展所用到的邊稱作「枝」,也就是說樹上的邊都是「枝」。一個點藉由邊往外延伸拓展,稱作「分枝branching」。

【註:為了方便,以下仍稱呼「邊」。】

root

「根」。方才提到,一棵樹可想做是由一個點開始分枝──這個點便是「根」。一棵樹上的每一個點都可以作為根。

leaf

「葉」。在一棵樹上選定根後,由根開始不斷分枝,途中所有無法繼續分枝的點皆是「葉」。

也可以不選定根,這種情況下,只連著一條邊的點都是「葉」。

如果樹上總共只有一個點,那麼此點既是根、也是葉。

level

「層」。在一棵樹上選定根後,按照拓展的順序(也就是按照每個點離根的距離),可以將樹上的點分層次,使得樹上每一個點都擁有一個層數。如果改變根,那麼分層的結果就會不同。

還有另一種比較少見的分層方式,是設定所有葉在同一層,由葉開始計算層數。

parent & child

「父親」與「小孩」。在一棵樹上選定根後,以邊相連的任兩點,靠近根者相對地稱作「父親」,靠近葉者相對地稱作「小孩」。

一個點的父親,是指此點相鄰的點當中,比此點更靠近根者。父親只會有一個,特例是:根沒有父親。

一個點的小孩,是指此點相鄰的點當中,比此點更靠近葉者。小孩可以是任意多個,特例是:葉沒有小孩。

ancestor & descendant

「祖先」與「子孫」。在一棵樹上選定根後,一個點的父親、父親的父親、……皆是此點的「祖先」。一個點的小孩、小孩的小孩、……皆是此點的「子孫」。

directed tree

在一棵樹上選定根後,可以把邊的方向設定成分枝的方向、遠離根的方向;也可以把邊的方向設定成朝向根的方向,但是這種情況比較少。

weight

一棵樹可以有權重。當邊擁有權重時,一棵樹的權重等於樹上所有邊的權重總和。

forest

「森林」。很多棵樹稱作一叢「森林」。只有一棵樹也是「森林」。

樹的特性

1. 樹沒有環。
2. 樹上所有點之間都相連通。
3. 沒有環的圖,就是樹或森林。
   沒有環的圖、連通的圖,就是樹。
4. 任意兩點之間只有唯一一條路徑。
5. 在樹上任意添加一條邊,就會產生環。
6. 在樹上任意刪除一條邊,一顆樹就裂成兩棵樹。
7. 邊數等於點數減一。

tree資料結構

同樣是edge list、adjacency matrix、adjacency lists。

一棵樹剛好V個點、V-1條邊,空間複雜度變低了。

edge list:空間複雜度變成O(E) = O(V-1) = O(V)。
adjacency matrix:空間複雜度仍是O(V²)。
adjacency lists:空間複雜度變成O(V+E) = O(2V-1) = O(V)。

tree traversal

同樣是DFS、BFS。

有根樹(有根森林)可以用一條陣列儲存每個點的父親。空間複雜度O(V)。

遍歷一棵樹與遍歷一張圖,概念完全相同,實作稍有不同。一棵樹,任意兩點之間只有一條路;只要避免走回頭路,就不必記錄每一點是否已經拜訪過。

UVa 615 599

tree property

先看個圖片

圖片中省略了點的編號。

distance

一棵樹、兩點之間的「距離」,就是兩點之間的邊數。

由其中一個點開始進行BFS或DFS即可。

UVa 1599

depth

一棵有根樹、每個點的「深度」,就是根到每個點的距離。

由根開始進行BFS或DFS即可。

height

一棵有根樹、每個點的「高度」,就是每個點到最遠的子孫的距離。最遠的子孫一定是葉。

運用divide-and-conquer method,移除根,形成許多子樹,分頭處理子樹。

divide-and-conquer method的運作順序,恰巧就是DFS的遍歷順序。

diameter

一張圖的「直徑」,是指最長的距離。

一棵無根樹的「直徑」,恰好是相離最遠的兩個點的距離。

稍微修改一下計算高度的程式碼,就可以順便計算直徑。

UVa 10308 11695 12379 12182

radius

一張圖的「半徑」,是選定一個起點,讓最長距離盡量短。

一棵無根樹的「半徑」,是選定一個根,讓樹的高度最小。

根位於直徑的中央,能讓樹的高度最小。

演算法請自行參考程式碼,時間複雜度是兩次DFS的時間。

UVa 10459 10939

tree operation

parent–child relationship

兩個點擁有「親子關係」時,一點是另一點的父親,一點是另一點的小孩。

建立DFS tree或BFS tree,判斷一點是不是另一點的父親。

ancestor–descendant relationship

兩個點擁有「祖孫關係」時,一點是另一點的祖先,一點是另一點的子孫。

建立DFS tree或BFS tree,第二個點持續找父親,直到遇見第一個點、或者遇見過根。

kth ancestor

一個點的所有祖先當中,往根方向數去第k個,稱作「第k祖先」。

方便起見,自己是第0祖先,自己可以是自己的祖先。

方便起見,輩分超過根時,用根代替。

建立DFS tree或BFS tree,連續找k次父親。

lowest common ancestor

兩個點的所有共同祖先當中,離根最遠、深度最深的那一個共同祖先,稱作「最低共同祖先」。

方便起見,自己可以是自己的祖先。

依序枚舉第一個點的所有祖先,存入表格。依序枚舉第二個點的所有祖先,查閱表格,判斷是否相符。