「樹」是一類重要的非線性資料結構，本文介紹了樹的基本概念、術語、性質，

一、樹的基本概念和術語

樹在生活中隨處可見

樹有許多特點：有一個樹根、樹根可以分出樹干，樹干可以分出許多樹枝、樹枝上有許多葉子，

樹作為一種資料結構，也有相似的特點

1. 樹是一個有限集合

2. 有且僅有一個特定的「根節點」（Root），如上圖中的結點A

3. 一顆樹的根可以有許多「子樹」，如根節點A有3顆子樹(T1、T2、T3)，這些子樹本身也是一棵樹，比如結點B又是樹T1的根節點，

4. 樹的結點包含「資料元素」和「若干指向其子樹的分支」

5. 結點的度（Degree）：結點擁有的子樹數，如結點A的度為3，結點C的度為1，結點G的度為0

6. 葉子（Leaf）或 終端結點：度為0的結點，如K

7. 非終端結點 或 分支節點：度不為0的結點，如結點A、E、C，

8. 內部結點：除根結點之外的分支節點，即在樹內部的結點，如結點B、C、E、H，

9. 孩子、雙親、兄弟、堂兄弟、祖先、子孫這些概念和族譜上的相同，

   如：A的孩子是B、C、D，A是B、C、D的雙親，B、C、D是兄弟(同一雙親)，F、G、H是堂兄弟(同一層但不同雙親)，K的祖先是E、B、A，B的子孫是B、E、F、K、L，

10. 層次：層次從根開始，根為第一層，根的孩子為第二層……

11. 深度（Depth）或 高度：樹中結點的最大層次，如樹T的深度為4，

12. 森林：即n(n≥0)顆互不相交的樹的集合

由上述特點我們可以看出，樹的結構是遞回的，樹T是一顆樹、其根結點A的子樹也是一棵樹、A的子樹的根節點的子樹也是一棵樹、A的子樹的根節點的子樹的根節點的子樹也是一棵樹……

二、二叉樹

1. 二叉樹的基本結構

二叉樹是一種特殊的樹，特點是每個結點至多只有兩顆子樹，所以二叉樹中不存在度大于2的結點，二叉樹的子樹有左右之分，次序不能任意顛倒，

二叉樹的5種基本形態：

1. 空二叉樹
2. 僅有根結點的二叉樹
3. 右子樹為空的二叉樹
4. 左子樹為空的二叉樹
5. 左右子樹都不為空的二叉樹

二叉樹的結構是遞回的，一個二叉樹或者為空，或者由一個根結點加上兩顆左右子樹構成的（這兩顆子樹也是二叉樹），

滿二叉樹和完全二叉樹是兩種特殊的二叉樹，

滿二叉樹的特點在于「滿」，即每層的結點數都是最大結點數，如下圖：

完全二叉樹的「完全」是相對于滿二叉樹來說的，下圖是一個完全二叉樹：

對一顆滿二叉樹和一顆完全二叉樹按「自上向下，自左向右」的順序進行編號，如上面兩個圖，完全二叉樹中的所有結點（1~12結點）必須和滿二叉樹中的1~12結點在位置上一一對應，

如下左圖為滿二叉樹，右圖為非完全二叉樹，因為其所有結點（1~6結點）和其對應的滿二叉樹中的1~6結點在位置上并不一一對應，

2. 二叉樹的遍歷

搞清了二叉樹的結構，那么如何遍歷它？

二叉樹的結構是遞回的，由根節點、左子樹、右子樹組成，所以我們只需遞回地遍歷這三個部分即可，根據遍歷這三個部分的順序的不同，有三種遍歷方式：

• 先序遍歷
• 中（根）序遍歷
• 后（根）序遍歷

(1) 先序遍歷

基本步驟：

1. 二叉樹不為空時，

   1. 訪問根結點
   2. 先序遍歷左子樹
   3. 先序遍歷右子樹

2. 二叉樹為空時，做空操作，

步驟描述：

1. 訪問根結點A
2. A有左孩子B，B是A的左子樹的根結點，訪問結點B
3. B有左孩子D，D是B的左子樹的根結點，訪問根結點D
4. D沒有左孩子
5. D沒有右孩子
6. 回傳到B
7. B有右孩子E，E是B的右子樹的根結點，訪問根結點E
8. E有左孩子G，G是E的左子樹的根結點，訪問根結點G
9. G沒有左孩子
10. G沒有右孩子
11. 回傳到E
12. E沒有右孩子
13. 回傳到A
14. A有右孩子C，C是A的右子樹的根結點，訪問根結點C
15. C沒有左孩子
16. C有右孩子F，F是C的右子樹的根結點，訪問根結點F
17. F有左孩子H，H是F的左子樹的根結點，訪問根結點H
18. H沒有左孩子
19. H有右孩子I，I是H的右子樹的根結點，訪問根結點I
20. I沒有左子樹
21. I沒有右子樹
22. 回傳到F
23. F沒有右子樹
24. 遍歷結束

所以與其說是在遍歷結點，不如說是在遍歷「根結點」，我們只是在遞回地把「所有根結點」找出來并輸出而已，（因為每個結點都可以看做是根結點）

(2) 中序遍歷

基本步驟：

1. 二叉樹不為空時，

   1. 中序遍歷左子樹
   2. 訪問根結點
   3. 中序遍歷右子樹

2. 二叉樹為空時，做空操作，

(3) 后序遍歷

基本步驟：

1. 二叉樹不為空時，

   1. 后序遍歷左子樹
   2. 后序遍歷右子樹
   3. 訪問根結點

2. 二叉樹為空時，做空操作，

3. 二叉樹、樹、森林

(1) 樹的遍歷

先根遍歷：先訪問樹的根結點，然后依次先根遍歷根的每顆子樹

后根遍歷：先依次后根遍歷每顆子樹，然后訪問根結點

(2) 森林的遍歷

先序遍歷：

若森林非空，則：

1. 訪問森立中第一棵樹的根結點
2. 先序遍歷第一棵樹的「根結點的子樹構成的森林」
3. 先序遍歷除去第一棵樹之后「剩余的樹構成的森林」

說白了就是，依次先根遍歷森林中的每棵樹，

中序遍歷：

若森林非空，則：

1. 中序遍歷森林中第一棵樹的「根結點的子樹構成的森林」
2. 訪問第一棵樹的根結點
3. 中序遍歷除去第一棵樹之后「剩余的樹構成的森林」

說白了就是，依次后根遍歷森林中的每顆樹，

森林的先序遍歷和中序遍歷即為其對應二叉樹的先序和中序遍歷，

(3) 二叉樹、樹、森林的轉換

樹和二叉樹的轉換：

給定一棵樹，可以找到惟一的一顆二叉樹與之對應，

轉換方法：

1. 按照「先根遍歷的次序」來轉化每個結點
2. 如果該結點是根結點，則作為二叉樹的根結點
3. 如果該結點是「第一個孩子」，則作為「上一個結點的左孩子」
4. 如果該結點「非第一個孩子」，則作為「上一個兄弟結點的右孩子」

說明：

1. 孩子的次序通常自左向右排序，如A的孩子BCD的次序為第一個、第二個、第三個
2. 「上一個結點」是指在先根遍歷次序中的上一個結點，
3. 「上一個兄弟結點」是指在原樹中的左面的兄弟結點，如E、F、G為兄弟，F的上一個兄弟結點為E，G的兄弟結點為F，

觀察樹對應的二叉樹，我們發現：

1. 「在二叉樹中，某個結點的左孩子」對應「在原樹中，該結點的第一個孩子」，
2. 「在二叉樹中，某個結點的右孩子」對應「在原樹中，該結點的兄弟節點」，

根據以上兩個特點，我們可以將二叉樹轉化為樹，

森林和二叉樹的轉換：

「森林和二叉樹的轉換」與「樹和二叉樹的轉換」規則類似，我們只需將森林中的每棵樹的根結點看做是兄弟結點，即將森林看做一棵樹，然后按照樹和二叉樹的轉換規則即可，

三、Huffman樹

1. 路徑：從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑

2. 路徑長度：路徑上的分支數目，

   如結點d的路徑長度為2

3. 樹的路徑長度：從樹根到每一個結點的路徑長度之和，

   上圖中樹的路徑長度為0+1+1+2+2+3+3=12

4. 結點的帶權路徑長度：從該結點到樹根之間的路徑長度與結點上的權的乘積，

   結點d的帶權路徑長度為2×4=8

5. 樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，

   上圖樹的帶權路徑長度為2×4+3×7+3×5+1×2=46

1. 最優二叉樹

樹的帶權路徑長度最小的二叉樹為最優二叉樹或Huffman(赫夫曼)樹，

上圖中的二叉樹并不是最優二叉樹，那么我們如何構造最優二叉樹？

1. 給定一個集合，該集合中有n顆二叉樹，每顆二叉樹都只有一個帶權的根結點，其左右子樹為空
2. 選取兩顆根結點的權值最小的樹作為左右子樹構造一顆新的二叉樹，新二叉樹的根結點的權值為其左右子樹上根結點的權值之和
3. 在集合中洗掉這兩棵樹，同時將新構造的二叉樹加入集合中
4. 重復步驟2、3，直到集合中只含一棵樹為止，該樹便是赫夫曼樹，

2. Huffman編碼

如果將電文中的字符A、B、C、D分別編碼為0、00、1、01，當發送方發送000011010時，接收方并不能準確翻譯，因為0000可能翻譯為AAAA或BB或AAB或BAA，

所以如果要設計長短不一的編碼，必須滿足任一個字符的編碼都不是另一個字符的編碼的前綴，這種編碼叫做前綴編碼，

我們可以利用二叉樹來設計前綴編碼：

4個葉子結點表示ABCD，約定左分支表示0，右分支表示1，從根節點到葉子結點的路徑上分支組成該葉子結點字符的編碼，A：0，B：10，C：110，D：1111，按這種方式得到的編碼編譯的電文并一定不是最短的，

如何得到使電文總長最短的二進制前綴編碼呢？

將字符出現的頻率作為權，設計一顆赫夫曼樹，由該赫夫曼樹得到的前綴編碼編譯的電文是最短的，這種編碼稱為赫夫曼編碼，

如有錯誤，還請指正

文章首發于公眾號『行人觀學』

標籤：其他

上一篇：劍指Offer(第二版)面試題目分析與實作-解決面試題的思路

下一篇：NTP時鐘服務器在標準化考場系統應用