三分鐘帶你了解樹與二元樹

在電腦領域，我們天天要處理的【資料夾】、資料庫中我們儲存的數據，都是樹的典型的應用。今天我們來學習的就是比較偏理論的關於樹和二元樹的定義以及它們的一些屬性特徵。

樹

從上面實際生活中的例子裡，我們可以看出，樹這種結構是可以歸納出它的一些特徵的。

樹 （Tree）是 N (N>0)個結點的有限集，它或為空樹（N=0）;或為非空樹 T 。

在這個定義中，我們需要明確兩個問題：一是樹一定是有結點的，二是根據結點數可以分為空樹和非空樹兩種。不過這只是最基本的定義，它還有一些特性。

有且僅有一個稱為根的結點。

也就是說，這個樹一定是從某一個結點開始擴展出來的，這個結點就向樹根一樣。從它開始向外開枝散葉。

除根結點以外的其餘結點可分為m ( m > 0 ) 個互不相交的有限集合T1，T2 …，Tm 其中每一個集合本身又是一顆樹，並且稱為根的子樹（SubTree）

這一段可能會不太好理解，其實說白了就是每個結點只有一個上級結點，不能有多個上級結點。同理，平級結點之間也不能有聯繫，但是它可以有多個下級結點。

關於樹的定義我們可以看下下面這個圖。

上圖中簡單的列舉了標準的樹和不標準的樹是什麼樣子的。其中：

• (a) ，是只有一個根結點的樹，只要有一個結點，它就可以稱為一個樹結構

• #(b) ，是一個標準的樹結構

• (c) ，注意它的C 和H 結點之間有一條連接線，這個就不是樹了，結點只能有一個上級結點的才稱為樹，這個其實就是我們將來要學的【圖】了

樹的相關術語

相對於堆疊的壓（入）堆疊、出棧，佇列的入隊、出隊來說，樹的相關術語可就複雜的多了。不論如何，首先你得先記住這些術語，要不後面講的東西用得那些術語只會讓你更暈。不過我們一時記不住也沒關係，先有個大概的印象，在後面的學習進程中遇到了再回來複習，這樣印象反而會更加深刻。

• 結點：一個結點可能包含一組數據，或指向其它結點的分支，可以看作是樹枝分叉的那個地方，(b)圖中A、 B、 C、 D、 E 等等這些都是結點

• #結點的度：結點擁有的子樹數量就叫做結點的度，其實就是它的下級子結點有幾個就是幾度，(b)圖中，C 結點的度為1 ， D 結點的度為3

• 樹的度：樹內各結點度的最大值，就是擁有最多子結點的度數是多少，這個樹的度就是多少，(b) 圖這個樹的度數為3

• 葉子：度為0的結點，也就是沒有子結點的結點，(b) 圖中的K 、 L 、 F 、 G 、 M 、 I 、 J 就是這顆樹的葉子結點

• #雙親和孩子：一個結點的子結點，就是它的孩子；對這些子結點來說，目前這個結點就是它的雙親，(b) 圖中，D 的孩子是 H 、 I 、 J ，而 H 、 I 、 J 的雙親就是D

• 層次：從根結點算起，根結點就是第一層，根的孩子就是第二層，依序類推，(b) 圖中G 結點所在的層次為3 ，(a) 圖的全部層次都只有1

• 樹的深度（高度）：目前這顆樹的最大層次，很明顯，(b) 圖的深度就是4

• 兄弟、祖先和子孫：兄弟結點就是這些結點的雙親是同一個結點；祖先結點就是從根結點到某個指定結點路上的經過的所有結點；子孫就是從某一個節點出發，到達目標結點這一路上的所有結點。 (b) 圖中， E、 F 是兄弟，E 的祖先是A 、 B ， E 的子孫為K 或L

• 堂（表）兄弟：所有在同一層的結點但雙親不同的結點都是堂兄弟，同樣還是在(b) 圖中，G 的堂（表）兄弟有 E、 F ，另外還有  H 、 I 、 J 也是它的表兄弟

二元樹

對樹的概念有了一定的了解之後，我們再來進一步的學習另一個概念，同時也是在資料結構和演算法中最重要的一種樹的形式：二元樹。

通常來說，樹的形狀是可以千變萬化的，例如一個結點可以有 3 個子結點，而另一個結點可能有 300 個子結點。這樣沒有什麼規則的樹其實操作起來會非常麻煩，而二元樹的定義就要簡單的多，除了有樹的性質外，它還多了一項內容：二叉樹的每個結點最多只有兩個子結點，也就是說，整個二元樹的度肯定是2 ，所有結點的度數都不會超過2 。關於二元樹為什麼好操作這一點，我們在下一小節的二元樹的性質中再詳細說明。所有的樹結構都是可以透過一定的規則變形來轉換成二元樹的。

我們同樣還是透過一張圖示來展示什麼是二元樹。

二元樹中，左邊的子結點及其子孫結點可以看成是關於目前結點的左子樹。右邊結點及其子孫結點也一樣可以看成是目前結點的右子樹。根據結點的子結點情況，就有了上面圖中的這幾種二元樹形態。

• (a) 樹是只有一個結點的樹，也可以說是只有一個結點的二元樹

• (b ) 樹是僅有一個左結點的二元樹

• (c) 樹是只有一個右結點的二元樹

• (d ) 樹是擁有左右兩個結點的二元樹

二叉樹的性質

性質1：在二元樹的第i 層上至多有2i-1 個結點（ i >= 1 ）

性質2：深度為k 的二元樹至多有2k - 1 個結點（ k >= 1）

性質3：對任何一顆二元樹T ，如果其終端結點數為n0 ，度為2的結點數為n2 ，則n0 = n2 1

性質4：具有n 個結點的完全二叉樹的深度為log2n 1

性質5：如果對一顆有n 個結點的完全二叉樹（其深度為log2n 1 ）的結點按層序編號（從第1層到第log2n 1 層，每層由左至右），則對任一結點i （ 1

1. 如果i = 1 ，則結點i 是二元樹的根，無雙親；如果i > 1 ，則其雙親是結點i / 2
2. 如果2i > n ，則結點i 無左孩子（結點i 為葉子結點）；否則其左孩子是結點2i
3. 如果2i 1 > n ，則結點i 無右孩子；否則其右孩子是結點2i 1

#關於二元樹的上述五個性質的數學證明我們就不詳細說了，畢竟我們這一系列的文章的宗旨也是希望透過簡單的範例讓大家學習到資料結構和演算法的精髓，而不是簡單粗暴的直接用數學公式來推導證明，那我們就直接來圖上數一數就好了。

• 對於性質1 來說，我們目前這個二元樹根據公式的話，在第3 層上最多只能有23-1 個結點，也就是4 個結點。第4 層上最多只能有24-1 ，也就是23 = 8 個結點

• 對於性質2 來說，目前這圖中的樹的深度為4 ，也就是最多有24 - 1 = 15 個結點

• 性質3 的話，我們先數數度為2 的結點有多少，在這個圖中，度為2 的結點有7 個，也就是A 、 B 、 C 、 D 、 E 、 F 、 G ，第4 層的結點都是沒有子結點的，也就是說它們都是0 度的，也稱為終端結點（葉子結點），這些結點的數量總共是8 個。現在n2 = 7 ，根據性質公式就可以得到n0 = n2 1 = 7 1 = 8

• 圖中的結點數為15 個，套用性質4 的公式可以得出log2n 1 = log215 1 = 3.91（向下取整） 1 = 3 1 = 4 ，當前樹的深度即為4 ，性質4 和性質2 可以看作是互補的

• 對於性質5 來說，請注意每個結點邊上的編號，我們就選取E 結點來作為範例說明。 E 結點目前為5 ，所以它的雙親為5 / 2 = 2 （向下取整）；E 的左孩子為2i ，也就是2*5=10 ，E 的右孩子為2i 1 ，也就是2 *5 1 = 11；性質5 的定義中說得更抽像一些，而且是拿葉子結點來做說明的，針對的是整個二叉樹的情況，但其實意思和我們這裡解釋的是一樣的，大家可以再拿其它結點驗證一下。性質5 對於後面我們要講的使用順序結構來儲存二元樹非常重要！

請務必掌握並記牢二叉樹的這五個性質及其意義，因為在後面的學習中，不管是二元樹的順序、鍊式儲存結構，或是二元樹的遍歷，都有可能接觸到上面的五個性質中的內容。可以說，它們就是二元樹學習中最最基礎的靈魂。

森林

最後，我們來簡單的了解下什麼是「森林」。多棵樹放在一起，就形成了一片「森林」。就像上文中二元樹的解釋圖一樣，(a)(b)(c)(d)放在一起將它們整體一起來看，就是一片“森林”，在這片“森林”中分別有著(a) (b)(c)(d)這四顆樹。

森林中的樹和樹之間是沒有聯繫的，如果我們要操作或遍歷一個森林的話，往往是將這片森林轉化為一顆樹。具體的演算法和步驟不是我們學習的重點，所以大家了解一下即可，有想深入研究的同學可以搜尋相關的內容或查閱相關的教材。

總結

從堆疊和佇列前進到樹後，是不是突然感覺到一下子就邁了一大步？有點搞不懂了？沒關係，今天的內容其實都是一些基礎的理論內容，能理解的就理解，不能理解的就接著繼續學習之後再返過來看今天的這些概念。

學習就不斷地重複進步地過程，當然一切都還是要以地基為基礎的。當你了解了樹的資料結構及一些簡單的遍歷演算法之後，再回來深入的理解這些概念並把他們背下來，相信一般的面試中關於樹相關的題目就不在話下了，一起努力吧！

推薦學習：php影片教學

以上是三分鐘帶你了解樹與二元樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！