樹 (圖論)
| 樹 | |
|---|---|
 包括6個頂點，5條邊的樹 | |
| 頂點 | v |
| 邊 | v - 1 |
| 色數 | 2 |
在圖論中，樹（英語：tree）是一種無向圖（英語：undirected graph），其中任意兩個頂點間存在唯一一條路徑。或者說，只要沒有環的連通圖就是樹。森林是指互相不交並樹的集合。樹廣泛應用於電腦科學的資料結構中，比如二元搜尋樹，堆，Trie樹以及用於資料壓縮的霍夫曼樹等等。
定義
[編輯]如果一個無向簡單圖 G 滿足以下相互等價的條件之一，那麼 G 是一棵樹：
如果無向簡單圖 G 有有限個頂點（設為 n 個頂點），那麼 G 是一棵樹還等價於：
- G 連通，有 n − 1 條邊，並且 G 中沒有環。
如果一個無向簡單圖 G 中沒有環，那麼 G 是森林。
性質
[編輯]一棵樹中任兩個頂點之間都有且只有一條路徑（指沒有重複邊的路徑）。一棵有 n 個頂點的樹有 n − 1 條邊，其為具有 n 個點連通圖的所需的最少邊數。所以如果去掉樹中的一條邊，樹就會不連通。
如果在一棵樹中加入任意的一條邊，就會得到有且只有一個環的圖。這是因為這條邊連接的兩個點（或是一個點）中有且只有一條路徑，這條路徑和新加的邊連在一起就是一個環。如果把一個連通圖中的多餘邊全部刪除，所構成的樹叫做這個圖的生成樹。
如果要在樹中加入一個點，就要加入一條這個點和原有的點相連的邊。這條邊不會給這棵樹增加一個環或者多餘的路徑。所以每次這樣加入一個點，就可以構成一棵樹。
一棵樹既可以是有向的也可以是無向的。顯然，樹是連通圖，但不會是雙連通圖（對於無向圖）或者強連通圖（對於有向圖）。樹可以算是稀疏圖。
顯然樹中也沒有自環和重複邊。
有根樹
[編輯]在一棵樹中可以指定一個特殊的節點：根。一個有根的樹叫做有根樹。
有根樹中的節點可以根據到根的距離分層。一顆有根樹的層數叫做這棵樹的高度。節點最多的那一層的節點數叫做這棵樹的寬度。對於有根樹，每條邊都有一個特殊的方向：指向根節點的方向，或者說上一層的方向（或者相反的，指向葉節點的方向，下一層的方向）。一條邊的兩個端點中，靠近根的那個節點叫做另一個節點的父節點（也叫父親、雙親、雙親節點），相反的，距離根比較遠的那個節點叫做另一個節點的子節點（也可以叫孩子，兒子，子女等）。父親方向的所有節點都叫做這個節點的祖先，兒子方向的所有節點都叫做這個節點的子孫。沒有子節點的子節點叫做葉節點（或者葉子節點）。由於到根的路徑只有一條，根節點以外的節點的父節點永遠只有一個，祖先就是這個點到根的路徑上的所有節點（包括根，不包括這個節點本身）。另外，以一個節點為根的樹是指包括這個節點和其所有子孫，並以這個節點為根的樹。由於一般不需要這以外的子樹，每一個節點也可以對應到一個以其為根的樹，一個節點的子樹通常也是指以這個節點的子節點為根的樹。
如果一顆有根樹每個節點的子樹最多有n個，同時每個節點在其父節點中都有固定的可能可以留空的位置，這棵樹叫做n叉樹。其中每個節點都可以有兩個固定位置的子樹的有根樹叫做二元樹，二元樹中每個節點的兩個子樹分別叫做左子樹和右子樹，由於位置固定，沒有左子樹的時候也是可以有右子樹的。而「多叉樹」通常並不指n為任意值的n叉樹，只是在和n叉樹作比較的時候表示普通的有根樹。
對於隨機的樹，高度的平均複雜度是O(logn)，但是沒有限制而且不隨機的樹高度也可以達到O(n)，也就是除了葉節點都只有一個子樹，或者常數個分支的情況。所以樹作為資料結構時通常需要另外進行平衡。
儲存
[編輯]對於普通的樹，可以像圖一樣為每一個點儲存一個邊表（通常按順序存和每一個點的關係的叫做鄰接矩陣，存具體的邊的叫做鄰接表），或者直接儲存所有邊的邊表等。由於樹是稀疏圖，所以一般不用鄰接矩陣儲存。對於有根樹，如果用為每一個點儲存一個邊表的方法，由於每一棵樹都只有一個父節點，所以通常指向父節點的邊不存在這個表中。同時如果子節點是沒有順序的，也是因為一個節點的子節點不會同時是其他節點的子節點，也可以把子節點直接當成存邊的鏈結串列的節點，這時候每個節點只需要儲存兩個指標，所以這種儲存方法有時候也會被叫做多叉樹轉二元樹。
對於子節點是有順序的有根樹，每條邊都可以以固定的位置分別儲存。對於完全二元樹甚至能直接用一個陣列訪問所有節點，不另外儲存邊的資訊。有的樹可以被設計成固定的從根節點開始訪問，這時候可以不儲存父節點。同樣的，有的樹也可以省略子節點，例如併查集。
樹的遍歷
[編輯]對於一般的樹，可以用和普通的圖一樣的方法遍歷，比如深度優先搜尋和寬度優先搜尋。如果和樹的每個節點相鄰的點有固定的順序，深度優先搜尋可以不儲存當前點以外的任何資訊，而且不用判重。而在有根樹中更方便，所以有根樹中很少使用寬度優先搜尋。
對於有根樹的從根開始的深度優先搜尋遍歷，有三種特定的順序：
- 前序遍歷
- 先訪問根節點，然後再訪問所有的子樹；
- 後序遍歷
- 先訪問子樹，然後再訪問根節點；
- 中序遍歷
- 二元樹專用，先訪問左子樹，然後是根節點，最後是右子樹。
注意對於每一種遍歷，事實上都得先訪問根節點，這裡的遍歷順序是指處理節點中的資料的順序。已知中序遍歷和任一其他遍歷的情況下，可以還原一個二元樹。一個直觀的方法是按前序或者反轉的後序插入一個按中序排序的搜尋樹。已知前序和中序也可以還原一棵樹，但是不能知道二元樹中一個節點唯一的子樹是在左邊還是右邊。
事實上也可以把左右的順序反過來。這些由根開始的遍歷方法也適用於特定的一個子樹。
森林
[編輯]森林比樹少一個條件，指沒有迴路的圖。也就是說，森林可能是不連通的，邊數可能比樹還少，就是說小於頂點數。
森林也可以看成是好多棵互不相連的非空的樹，只有一棵樹也可以算是森林。不過森林不一定是一棵樹。
森林也可以是有根的，這時候森林中的每一棵樹都有一個根。
一棵樹去掉若干條邊也會成為森林，這時候可以看成一棵樹分成了好多棵樹。森林中的兩棵樹之間加一條邊，也可以把這兩棵樹合在一起，最終合成一棵樹。
很多地方用森林，都是用來表示很多棵樹，包括作為邏輯結構、資料結構的時候等。有一種重要的資料結構併查集就是一個有根的森林，可以很快的判斷兩個元素是不是屬於同一個互相獨立的集合，以及合併兩個集合等。
邏輯結構
[編輯]樹也通常會用來表示邏輯結構，例如搜尋樹。表示邏輯結構的樹一般是有根樹。這種結構類似於有拓撲序的圖，每個節點是其之前的節點的後繼、分支、子節點等。樹的結構中，每個節點之前的節點是唯一的（就是說有唯一的前驅、上層容器、父節點等），另外每一個節點及其後面的部分也都是一棵樹。
作為資料結構
[編輯]樹也是一類重要的資料結構，同時也有邏輯結構的性質，通常也是有根樹。主要有搜尋樹和堆兩種，前者的內容是按中序遍歷的順序排序的，後者每個節點的關鍵字都比它的子節點大（或者小）。複雜度一般在樹的高度，也就是O(nlogn)以內。
搜尋樹可以快速的尋找有序的內容或者新內容在已有內容中的位置，也可以進行一些和按這個順序的範圍有關的統計。
堆 (資料結構)是一種優先佇列，比搜尋樹功能少，通常只能很方便的求堆中關鍵字最小（最大）的資料，不能尋找。（當然有的時候求次小和第三小也是很方便的）
很多這類資料結構會給每個點或者邊加上一些別的參數。有些資料結構還會破壞本來的樹的結構，但是基本還是用的樹的模式，一般還是叫做「樹」。