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)。

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

bool adj[9][9]; // adjacency matrix int parent[9]; // DFS tree void DFS(int x) { for (int y=0; y<9; ++y) if (adj[x][y]) if (y != parent[x]) // 避免走回頭路 { parent[y] = x; DFS(y); } }

UVa 615 599

先看個圖片

圖片中省略了點的編號。

Distance

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

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

bool adj[9][9]; // adjacency matrix int distance[9]; // 根到每個點的距離 void DFS(int x, int px) // px是x的父親 { for (int y=0; y<9; ++y) if (adj[x][y] && y != px) { distance[y] = distance[x] + 1; DFS(y, x); } } void tree_distance(int x, int y) { distance[x] = 0; DFS(x, x); cout << x << "到" << y << "的距離是" << distance[y]; }

UVa 1599

Depth

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

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

bool adj[9][9]; // adjacency matrix int depth[9]; // 每個點的深度 void DFS(int x, int px) // px是x的父親 { for (int y=0; y<9; ++y) if (adj[x][y] && y != px) { depth[y] = depth[x] + 1; DFS(y, x); } } void tree_depth(int root) { depth[root] = 0; DFS(root, root); for (int i=0; i<9; ++i) cout << "節點" << i << "的深度是" << depth[i]; }

Height

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

運用Divide-and-Conquer Method，移除根，形成許多子樹，分頭處理子樹。

Divide-and-Conquer Method的運作順序，恰巧就是DFS的遍歷順序。

bool adj[9][9]; // adjacency matrix int DFS(int x, int px) // px是x的父親 { int h = 0; for (int y=0; y<9; ++y) if (adj[x][y] && y != px) h = max(h, DFS(y, x) + 1); return h; } void tree_height(int root) { cout << "整棵樹的高度是" << DFS(root, root); }

Diameter

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

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

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

bool adj[9][9]; // adjacency matrix int diameter = 0; int DFS(int x, int px) // px是x的父親 { int h1 = 0, h2 = 0; // 記錄最高與次高的高度 for (int y=0; y<9; ++y) if (adj[x][y] && y != px) { int h = DFS(y, x) + 1; if (h > h1) h2 = h1, h1 = h; else if (h > h2) h2 = h; } diameter = max(diameter, h1 + h2); return h1; } void tree_diameter() { diameter = 0; // 初始化 int root = 0; // 隨便選一個根 DFS(root, root); cout << "樹的直徑是" << diameter; }

UVa 10308 11695 12379 12182

Radius

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

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

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

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

bool adj[9][9]; // adjacency matrix int parent[9]; // DFS tree int h1[9], h2[9]; // 記錄最高與次高的高度 int c1[9], c2[9]; // 記錄最高與次高的來源 void record(int x, int height, int child) { if (height > h1[x]) { h2[x] = h1[x]; c2[x] = c1[x]; h1[x] = height; c1[x] = child; } else if (height > h2[x]) { h2[x] = height; c2[x] = child; } } void DFS1(int x) { h1[x] = h2[x] = 0; for (int y=0; y<9; ++y) if (adj[x][y]) if (y != parent[x]) { parent[y] = x; DFS1(y); record(x, h1[y] + 1, y); } else ; // 由父親過來的高度，只能留待下一波解決。 } void DFS2(int x) { if (parent[x] != x) // 根沒有父親，不必算。 { int y = parent[x]; // 上一波沒解決的部分 // 之前記錄次高的高度，用意在於這裡！ // 當y的最高高度來源是x， // 此時y的次高高度，對x來說才是由y過來的高度。 if (c1[y] == x) record(x, h2[y] + 1, y); else record(x, h1[y] + 1, y); } for (int y=0; y<9; ++y) if (adj[x][y]) if (y != parent[x]) DFS2(y); } void tree_radius() { int root = 0; // 隨便挑一點當作根皆可 parent[root] = root; DFS1(root); DFS2(root); int radius = 1e9; int diameter = 0; // 順便算直徑 for (int x=0; x<9; ++x) { radius = min(b_height, h1[x]); diameter = max(diameter, h1[x]); } cout << "樹經過平衡之後的高度是" << radius; cout << "樹的直徑是" << diameter; for (int x=0; x<9; ++x) if (h1[x] == radius) cout << "可以作為根的點為" << x; for (int x=0; x<9; ++x) if (h1[x] == diameter) cout << "可作為直徑的端點有" << x; }

UVa 10459 10939

Parent–Child Relationship

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

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

bool adj[9][9]; // adjacency matrix int parent[9]; // DFS tree void DFS(int x) { for (int y=0; y<9; ++y) if (adj[x][y] && y != parent[x]) { parent[y] = x; DFS(y); } } bool x_is_parent_of_y(int x, int y) { return x == parent[y]; } void parent_child(int root) { parent[root] = -1; DFS(root); int x, y; while (cin >> x >> y) if (x_is_parent_of_y(x, y)) cout << "x是y的父親"; else if (x_is_parent_of_y(y, x)) cout << "y是x的父親"; else cout << "xy不是父子關係"; }

Ancestor–Descendant Relationship

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

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

bool x_is_ancestor_of_y(int x, int y) { for (y = parent[y]; y != -1; y = parent[y]) if (y == x) return true; return false; }

kth Ancestor

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

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

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

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

int kth_ancestor(int x, int k) { for (int i=0; i<k ++i) if (parent[x] != -1) x = parent[x]; return x; }

Lowest Common Ancestor

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

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

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

bool ancestor[9]; int lowest_common_ancestor(int x, int y) { for (int i=0; i<9; ++i) ancestor[i] = false; for (; x != -1; x = parent[x]) ancestor[x] = true; for (; y != -1; y = parent[y]) if (ancestor[y]) return y; return y; // 不會執行到這一行。再不濟也總會遇到根。 }