樹的概念

什麼是樹

樹 (Tree) 是一種資料結構，實際上就是圖論中的一個特例，許多演算法在樹上和圖上都是通用的。不過由於樹的結構有許多特點，因此特別拿出來介紹。

樹存在以下幾個性質：

1. 由 $n$ 個點及 $n-1$ 條邊所組成。
2. 任意兩點之間存在唯一的路徑。
3. 樹中不存在環。

在解題中，樹的性質常常可以幫助我們簡化問題。

有根與無根

大致上，樹可以分為有根樹 (Rooted Tree) 與無根樹 (Unrooted Tree) 兩種。

有根樹是指樹中有一個特定的節點稱為根節點，且該根節點不會有任何的 in degree，而無根樹則是沒有根節點的樹。

以這張圖為例，這就是一顆有根樹，根節點為 $1$。

而這張圖則是一棵無根樹，實作上，我們通常會任意選擇一個節點當作根節點來處理。

建立一棵樹

在 C++ 中，我們可以直接使用跟圖論相同的方式來建立一棵樹，也就是使用鄰接串列或鄰接矩陣。比較需要注意的地方是，有根樹要使用有向圖，而無根樹則使用無向圖來建立。

// 讀入 n-1 條邊
for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    // 有根樹建有向邊
    adj[u].push_back(v);
    // 無根樹建無向邊
    adj[u].push_back(v);
    adj[v].push_back(u);
}

不過有根樹中，其實還有幾種儲存樹狀圖的流派，比如對於每個節點，我們可以儲存其父節點，或是儲存其子節點，這兩種方式各有優缺點，可以依照題目需求來選擇，甚至是所有的方式都同時使用。