樹的基本性質 Basic Properties of Trees

樹是圖論中一種很常見的圖，在電腦科學中更是不可或缺的一種資料結構。由於其特殊性，相關應用也相當廣泛，是競程不可或缺的題型之一。很多人把樹當作是一門學問獨立出來稱作「樹論」，但嚴格上來說不能這樣稱呼，因為他就是一種特殊結構的圖而已，基本上出了中文競程圈就完全聽不到這種叫法

本文會介紹樹的定義、性質與用途

簡介

澄清

首先，資工的樹長下圖右邊的樣子 : 根在上、葉在下
別人覺得你畫這樣有病是正常的 XD

常見例子

生活中最常遇到的樹通常會有「上對下」的關係，像是祖譜、企業的組織圖等等

電腦中的例子

在儲存檔案資料時，都是使用樹狀結構，因為其特性可以 (比較) 輕鬆找到資料
在資料結構中，只要加入一些特性，就可以更好地儲存/刪除/查詢資料

常見的有 :

• 二元搜尋樹
• 紅黑樹
• B-tree
• Binary Heap
• Binomial Heap
• Fibonacci Heap

還有一些樹，實際上並不存在，但是在抽象的計算機理論中佔有一席之地的樹 :

• Parsing Tree (在 formal language 中，這種樹代表語言產生的「過程」)
• Search Tree (每個節點都代表一個狀態，早期的 AI 很常見)

競程會用到的樹

這些不是本篇重點，只稍微提一下名詞 :

• 一般的樹
• 線段樹 (segment tree，用於處理區間問題)
• Binary Indexed Tree (處理區間問題，主要是前綴和)
• 生成樹 (一種很特別的子圖)
• 併查集 (DSU，一種維護集合的樹狀資料結構)

樹的定義與名詞

定義

每份資料中，樹的定義都長得有所不同。以下列出幾個常見的定義 :

給定一張

$n$ 節點的圖

$G$ (其中

$n\ge 1$)
A)

$G$ 連通且沒有環
B)

$G$ 是連通且只有

$n-1$ 條邊
C)

$G$ 只有

$n-1$ 條邊且沒有環
D)

$G$ 沒有自環且所有點對

$u,v$ 都只存在一條路徑

以上四種定義其實都互相等價，證明很簡單，可以自己玩玩看

森林 Forest

一張由好幾棵樹組成的圖，每棵樹之間是不連通的。其實把定義 A 當中的「連通」拿掉，就是森林

森林正式的定義 : 無環圖

距離 Distance

若一張圖

$G$ 存在

$u,v$ 路徑，則

$d(u,v)$ 為從

$u$ 到

$v$ 的最少的邊數，有時會直接稱為「距離」或是「最短距離」。若

$G$ 則不存在

$u,v$ 路徑，則

$d(u,v)=\mathrm{\infty }$ (要看怎麼用)。若

$G$ 為一棵樹，則

$u,v$ 路徑唯一 (根據定義 D)

直徑 Diameter

直徑就是所有點對最短距離的最大值 (很饒口沒錯，所以看符號就好)

$ma{x}_{u,v\in V(G)}d(u,v)$

根

一棵樹只會有一個節點作為根，稱作根節點。一棵樹的每個節點都可以是根節點，通常固定下來就不會換 (視情況而定)

葉

一棵樹可能有多個葉，稱作葉節點。度數為一 (只有一個鄰居) 的節點，就是葉節點。與根節點不同，一棵樹的葉節點都是固定不變的

有時一個節點可能會同時是根也是葉，視情況而定

綠色為葉節點、橘色為根節點

常用的樹的性質

深度

與根節點的距離，稱為深度。在很多演算法中，樹的深度決定了複雜度

親屬關係

父節點

給定一個節點

$x$，若存在深度比

$x$ 少

$1$ 且與

$x$ 為鄰居的節點，則稱其為

$x$ 的父節點

備註 : 除了根節點之外，每個節點的父節點唯一

子節點

給定一個節點

$x$，若存在深度比

$x$ 多

$1$ 且與

$x$ 為鄰居的節點，則稱其為

$x$ 的子節點

祖先

給定一個節點

$x$，則

$x$ 的祖先為

$x$ 到根節點的路徑上所有的節點 (不包含

$x$)

備註 : 根節點是圖中大家的祖先，且沒有父節點

舉例說明

以下圖為例

• $d$ 為根，深度為
  $0$，是大家的祖先
• $e$ 是
  $b$、
  $c$ 的父節點
• $b$、
  $c$ 是
  $e$ 的子節點

綠色為葉節點、橘色為根節點

樹的子圖

若一個樹的子圖是不連通的，則為森林，反之則為樹

若特別強調某個節點

$x$ 的後代所形成的樹，則稱為

$x$ 的子樹

其他樹的性質

樹的每一條邊都是 cut-edge

在一張連通圖中，刪除 cut-edge 可以把圖變得不連通

一個 cut-edge 不能存在於任何環之中 (這是定理，玩玩看)。由於樹中不存在環 (根據定義 A)，不存在一條邊屬於任一個環，因此每條邊都是 cut-edge

樹加上一條邊就會形成環

根據定義 D，每個點對都存在唯一的路徑。若對點對加上一條邊，路徑就會不唯一，因而形成環

樹是一種二分圖

有關二分圖的定義可以看這篇

一張圖是二分圖若且唯若不存在奇數環 (這是定理可以自己證證看)。由於樹不存在奇數環 (根據定義 A，根本就沒有環)，因此樹是一種二分圖

至少兩片葉子

一個兩個節點以上的樹，至少有兩個葉節點

備註 : 這看起來很 trivial，但是在玩 Prüfer Code 時常被忽略

雜談

這邊純屬經驗談。總結來說，上面的說明看起來很容易，但那些定義與名詞都是屬於數學的範疇，我們肉眼看著圖很容易就可以找出想要找的點 (比如說祖先、直徑…等等)。實際上，要在電腦跑起來是一件很費力的事情，這要考量到資料量的大小、複雜度分析與對題目的觀察。這也是數學圖論與演算法圖論差異最大的地方

以我自己的經驗來說，一開始學的是演算法視角的圖論。時常要使用各種複雜的資料結構維護一堆東西，既複雜又麻煩。然而，在我接觸數學視角的圖論後，發現很多東西只要「存在」就好，實際找出「實例」的反而比較少，這也大大地簡化對圖論的想像，尤其是樹

若沒有對圖的想像、沒有數學視角的圖論，在接觸演算法時常常會不知道每個陣列在存什麼鬼。因此我認為先講清楚定義是必須的，之後幾篇筆記在樹的單元中，我也會先講定義 (或證明)，才會開始聊關於演算法及解題的事情

其實主要想講關於樹的主題就只有以下 :

• 圖的生成樹 : Cayley's formula、Matrix-tree theorem、最小生成樹
• 求一些樹的性質 : 最低共同祖先、直徑、中心、重心
• 把樹簡化成好解的樣子 : 樹壓平、輕重鏈剖分、倍增法

還有就是想抱怨一下，不知道為什麼一堆人都講「樹論」。樹什麼時候從圖論獨立出去變成一個理論了?? 人家歐美的任何競程網站也沒在講 "tree theory" 的啊! 到底哪個天才發明這個詞的啊? 真是亂來ㄟ

---

參考資料

• D.B.West - Introduction to Graph Theory 2/e
• 台師大演算法筆記 - tree
• CSES Competitive Programmer’s Handbook
• 海大競程 - 圖上遍歷 & 樹論

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2025/6/20