樹

樹(7張)

樹（tree）是包含 n(n≥0) ^[2]  個節點，當 n=0 時，稱為空樹，非空樹中

條邊的有窮集，在非空樹中：

（1）每個元素稱為節點（node）。

（2）有一個特定的節點被稱為根節點或樹根（root）。

（3）除根節點之外的其餘數據元素被分為

個互不相交的集合

，其中每一個集合

本身也是一棵樹，被稱作原樹的子樹（subtree）。

樹也可以這樣定義：樹是由根節點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關係構成的。集合中的元素稱為樹的節點，所定義的關係稱為父子關係。父子關係在樹的節點之間建立了一個層次結構。在這種層次結構中有一個節點具有特殊的地位，這個節點稱為該樹的根節點，或稱為樹根。

樹中的節點具有明顯的層級關係，並且一個節點可以對應多個節點。 ^[3] 

我們可以形式地給出樹的遞歸定義如下:

單個節點是一棵樹，樹根就是該節點本身。

設

是樹，它們的根節點分別為

。用一個新節點

作為

的父親，則得到一棵新樹，節點n就是新樹的根。我們稱

為一組兄弟節點，它們都是節點

的子節點。我們還稱

為節點n的子樹。

空集合也是樹，稱為空樹。空樹中沒有節點；

孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；

節點的度：一個節點含有的子節點的個數稱為該節點的度；

葉節點或終端節點：度為0的節點稱為葉節點；

非終端節點或分支節點：度不為0的節點；

雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；

兄弟節點：具有相同父節點的節點互稱為兄弟節點；

樹的度：一棵樹中，最大的節點的度稱為樹的度；

節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；

樹的高度或深度：樹中節點的最大層次；

堂兄弟節點：雙親在同一層的節點互為堂兄弟；

節點的祖先：從根到該節點所經分支上的所有節點；

子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫；

森林：由

棵互不相交的樹的集合稱為森林。

無序樹：樹中任意節點的子結點之間沒有順序關係，這種樹稱為無序樹,也稱為自由樹；

有序樹：樹中任意節點的子結點之間有順序關係，這種樹稱為有序樹；

二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；

滿二叉樹：葉節點除外的所有節點均含有兩個子樹的樹被稱為滿二叉樹；

完全二叉樹：除最後一層外，所有層都是滿節點，且最後一層缺右邊連續節點的二叉樹稱為完全二叉樹；

哈夫曼樹（最優二叉樹）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹。

定義一棵樹的根結點層次為1，其他結點的層次是其父結點層次加1。一棵樹中所有結點的層次的最大值稱為這棵樹的深度。

樹的表示方法有很多種，最常用的是圖像表示法。

以下是一個普通的樹（非二叉樹）：

用括號先將根結點放入一對圓括號中，然後把它的子樹由左至右的順序放入括號中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最後用閉括號括起來。如前文樹形表示法可以表示為：

遍歷表達法有4種方法：先序遍歷、中序遍歷、後序遍歷、層次遍歷

例如右圖：

其先序遍歷（又稱先根遍歷）為ABDECF（根-左-右）

其中序遍歷（又稱中根遍歷）為DBEAFC（左-根-右）（僅二叉樹有中序遍歷）

其後序遍歷（又稱後根遍歷）為DEBFCA（左-右-根）

其層次遍歷為ABCDEF（同廣度優先搜索）