方法還原成一般的樹。

5、樹的遍歷

由樹結構的定義可知，樹的遍歷有二種方法。

(1) 先序遍歷：先訪問根結點，然後依次先序遍歷完每棵子樹。如圖，先序遍歷的次序是：

AbcdEFGIJhK

(2) 後序遍歷：先依次後序遍歷完每棵子樹，然後訪問根結點。如圖，後序遍歷的次序是：

cdbFIJGhEKA

樹的先序遍歷實質上與將樹轉換成二叉樹後對二叉樹的先序遍歷相同。

樹的後序遍歷實質上與將樹轉換成二叉樹後對二叉樹的中序遍歷相同

【2019 年】若將一棵樹 t 轉化為對應的二叉樹 bt，則下列對 bt 的遍歷中，其遍歷序列

與 t 的後根遍歷序列相同的是（）

A.先序遍歷 b.中序遍歷 c.後序遍歷 d.按層遍歷

【2020 年】已知森林 F 及與之對應的二叉樹 t，若 F 的先根遍歷序列是 a, b, c, d, e, f，中

根遍歷序列是 b, a, d, f, e, c 則 t 的後根遍歷序列是：

A、b, a, d, f, e, c b、b, d, f, e, c, a c、b, f, e, d, c, a d、f, e, d, c, b, a 考點 15：哈夫曼樹(★★★)

1、最優二叉樹(huffman 樹)

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

2 路徑長度：結點路徑上的分支數目稱為路徑長度。

3 結點的帶權路徑長度：從該結點的到樹的根結點之間的路徑長度與結點的權(值)的乘積

4權(值)：各種開銷、代價、頻度等的抽象稱呼。

5樹的路徑長度：從樹根到每一個結點的路徑長度之和。

2、huffman 樹的構造

1 根據 n 個權值{w1, w2, ? ,wn}，構造成 n 棵二叉樹的集合 F={t1, t2, ? ,tn}，其中每棵二

叉樹只有一個權值為 wi 的根結點，沒有左、右子樹；

2 在 F 中選取兩棵根結點權值最小的樹作為左、右子樹構造一棵新的二叉樹，且新的二

叉樹根結點權值為其左、右子樹根結點的權值之和；

3 在 F 中刪除這兩棵樹，同時將新得到的樹加入 F 中；

4 重複2、3，直到 F 只含一顆樹為止。

構造 huffman 樹時，為了規範，規定 F={t1,t2, ? ,tn}中權值小的二叉樹作為新構造的二叉樹

的左子樹，權值大的二叉樹作為新構造的二叉樹的右子樹；在取值相等時，深度小的二叉樹

作為新構造的二叉樹的左子樹，深度大的二叉樹作為新構造的二叉樹的右子樹。

圖是權值集合 w={8, 3, 4, 6, 5, 5}構造 huffman 樹的過程。所構造的 huffman 樹的 wpL

是： wpL=6x2+3x3+4x3+8x2+5x3+5x3 =79。

3、huffman 編碼方法

由於每個字元都是葉子結點，不可能出現在根結點到其它字元結點的路徑上，所以一個

字元的 huffman 編碼不可能是另一個字元的 huffman 編碼的字首。

若字符集 c={a, b, c, d, e, f}所對應的權值集合為 w={8, 3, 4, 6, 5, 5}，如圖所示，則字元

a,b, c,d, e,f 所對應的 huffman 編碼分別是：10，010，011，00 ，110，111。

以字符集 c 作為葉子結點，次數或頻度集 w 作為結點的權值來構造 huffman 樹。規定

huffman 樹中左分支代表“0”，右分支代表“1” 。

從根結點到每個葉子結點所經歷的路徑分支上的“0”或“1”所組成的字串，為該結

點所對應的編碼，稱之為 huffman 編碼。