[概念辨析 系列 之四] 樹的概念

剛做老師的時候，在考試、面試等場合發現大家對計算機科學中"樹"的概念理解地非常不好，各種邏輯混亂的答案頻繁出現。當時還不太理解，過了一段時間之後，對這個問題有了更全面的認識。"樹"在不同場合有不同含義，這些含義之間是有關聯的，還經常混合著使用，因而也是易混淆的。更重要的是，在目前的教學中，不同課程對「樹」有不同的定義與解讀，而這些不同場合的解讀，是互相割裂的，缺乏全面、綜合的討論。因而打算在這裡系統地討論一下"樹"的概念，包括樹的基本定義，以及多種概念混合的樹。

1. 兩種基本的"樹"

樹的含義有不止一種，但是對於《演算法設計與分析》課程而言，我認為最重要的含義是圖論中樹的概念：

給定一個無向圖G，如果：i）G是連通的；ii）G是無環的，則G是一棵樹。

這一定義簡單明了，看起來不會弄錯的樣子。但是問題恰恰出在這裡：這一樹的概念非常有用，有用到我們經常把它跟其它概念混在一起使用，因而很容易導致混淆。

大家同樣比較熟悉的可能是數據結構中的二叉樹，以及其它類似的各種樹。這裡不在作詳細定義，可以參見以前文章中討論過的二叉樹中的一些概念。

參見"二叉樹相關的一些定義"中的討論

2. "樹"中到底有沒有根、父子、高度、深度等概念？

很多同學被問到什麼是樹的時候，第一反應是，有一個根，長出來，因而有父節點、子節點、左右兄弟節點、葉節點，有高度、深度等等。

對於圖論中的樹而言，最重要的defining characteristic是「無環」。連不連通（也就是說是一棵樹，還是一個森林）經常差別不大。例如我們演算法課中的很多問題，都是針對圖的一個連通片來考慮的，不同連通片分別作類似地處理即可。

圖論中樹是沒有根的概念的，也就無所謂父子、兄弟、左右子節點、高度、深度等等（圖論中的樹，有葉的概念，指度為1的節點）。

根節點、父/子節點、左/右子節點、兄弟節點、葉節點、高度、深度等都是數據據結構中二叉樹（以及其它類似的樹）中的概念。另外需要注意的是，有了根之後，樹中的邊就天然地有了方向的概念（不管你用不用它），我們可以自然地定義樹中的邊的方向是父指向子（或者反之）。

所以談到「樹」，大家腦子裡首先要弄清楚上述不同的定義，其次根據上下文判斷具體所談的是哪一種樹。

3. 很多大家熟知的樹，其實多種概念的混合體

大家混淆樹的各種概念，一個很可能的原因是很多重要的樹，其實是上述兩種概念的混合體。最典型的例子就是DFS/BFS遍歷樹。

我們討論圖遍歷的時候，所有tree edge組成了圖的遍歷樹（只考慮連通的情況。另外，如果對tree edge的概念不熟悉，可以翻書仔細回顧一下tree edge，forward edge，back edge，cross edge的概念）。我們之所以稱它為樹，主要是取了樹在圖論中的含義，即連通，無環。圖論中樹的概念，很好地概括了圖遍歷的一個重要屬性：走遍所有節點，且發現新節點的過程是反對稱的（無環的）。

但是遍歷樹的概念又顯然超出了圖論中樹的概念。

• 首先，遍歷樹它有天然的根節點，就是遍歷的起始節點，因而也就有父子節點、兄弟節點、葉節點、高度、深度等概念；

• 另外別忘了，雖然圖論中的樹是限於無向圖的，但是遍歷樹天然有方向。對於無向圖而言，雖然邊上本來沒有方向，但是遍歷中逐步發現新節點的過程，為每一條tree edge定義了一個方向，以tree edge的方向為基礎，forward edge，back edge，cross edge也就可以自然地定義方向。

• 最後，對於有向圖，講起來還更啰嗦一點。圖論中的樹都是針對無向圖的。對於有向圖，"連通"這一在無向圖中很簡單的概念，就需要更精細的討論，由此引申出強連通，弱連通等概念。對於有向圖，嚴格來說我們應該這麼講：如果對於有向圖的遍歷能夠走遍圖中所有的點，那麼我們取所有tree edge，並且忽略所有邊的方向，我們總會得到一棵生成樹（連通、無環）。正是在這個意義上，我們對有向圖，也同樣稱之為遍歷樹。有向圖的遍歷樹中的邊，以及其它各種邊當然有方向，就是它本來的方向。有向圖的遍歷樹同樣也有根、父子、高度、深度等概念。

最後，Prim演算法和Dijkstra演算法本質也是一種遍歷，只不過多了貪心選擇的過程，在我們的課本（《演算法設計與分析》）中把它們稱為Best First Search (BestFS)。因而Prim和Dijkstra演算法同樣有遍歷樹，它也同樣是上述多種樹的概念的混合體。大家可以結合上面的討論，來體會這兩個演算法執行過程中的連通性、無環性、方向性，以及根的概念、父子的概念等。

推薦閱讀：