第六章 樹狀結構 T r e e 版權屬作者所有，非經作者 同意不得用於教學以外用途.

Presentation on theme: "第六章 樹狀結構 T r e e 版權屬作者所有，非經作者 同意不得用於教學以外用途."— Presentation transcript:

1 第六章 樹狀結構 T r e e 版權屬作者所有，非經作者 同意不得用於教學以外用途

2 本章內容 6-1 樹及定義 6-2 二元樹的基本性質 6-3 二元樹的儲存方式 6-4 二元樹的建立 6-5 二元樹的走訪
6-1 樹及定義 6-2 二元樹的基本性質 6-3 二元樹的儲存方式 6-4 二元樹的建立 6-5 二元樹的走訪 6-6 引線二元樹 6-7 二元搜尋樹 6-8 高度平衡二元樹 (AVL樹) 6-9 m 元搜尋樹及 B 樹 樹 樹與紅黑樹 6-12 Huffman 樹

3 6-1 樹及定義 董事長 總經理 主任秘書 業務經理 人事經理 總務經理 秘書甲 秘書乙 國內部副理 國外部副理 採購主任 庶務主任 第五章提到，樹在數學上的定義是：沒有環路的連通圖，我們稱這種樹為「一般樹」( general tree ) 或是「無根樹」( unrooted tree ) 在資料結構中所應用的樹，我們稱之為「有根樹」( rooted tree )，有一個特定的節點稱為「樹根」( root )。樹根通常畫在一棵樹的最上方。樹根又包含零個到多個「子樹」( subtree )，畫在樹根的下方。 例如圖6.1中，董事長即為樹根。此樹根包含兩個子樹，分別是以總經理為樹根的子樹，和以主任秘書為樹根的另一子樹。

4 1. 內部節點 ( internal node ，或非終端節點 ， non-terminal node ) ： 節點 A、B、C、G
階度 ( level) 1 A B C D 2 E F G 3 H I J 4 1. 內部節點 ( internal node ，或非終端節點 ， non-terminal node ) ： 節點 A、B、C、G 2. 外部節點 ( external node ，或終端節點 terminal node ，或樹葉 leaf node ) ：節點 D、E、F、H、I、J 3. 節點 A 是節點 B、C、D 的父節點。節點 B、C、D 是節點 A 的子節點 4. 在第 2 階的節點有 B、C、D 5. 這棵樹的高度是 4 6. 所有的樹，節點數 ( V ) = 邊數 ( E ) + 1 除了樹根以外，其餘每個節點都有一個對應的邊從它的父節點指向它自己，因此節點數會比邊數多1，而多出來的節點就是樹根

5 6-2 二元樹的基本性質 … … … 1. 二元樹第 i 階上所有節點的數目最多為 2i-1 個
6-2 二元樹的基本性質 階度 ( i ) 2i-1 1 1 (21-1) 二元樹：每個內部節點最多有2個兒子 2 2 (22-1) 3 4 (23-1) … … … 4 8 (24-1) 1. 二元樹第 i 階上所有節點的數目最多為 2i-1 個 2. 高度為 k 的二元樹上所有節點的數目最多為 2k -1個 3. 完滿(full)二元樹：高度為 k 且總節點數為 2k -1的二元樹 高度為 4 的完滿二元樹 總節點數為 24 –1 = 15

6 4. 高度為 k 的二元樹上所有節點的數目最少為 k 個
5.若是所有內部節點都正好有兩個子節點，這種二元樹稱為正規二元樹 ( formal binary tree ) 外部節點數目 t 比內部節點數目 i 多一 t = i + 1 6.如果二元樹的排列情形如下：第 k 階滿了才能排到第 k+1 階，並且每一階的節點都是往左靠 ，這種二元樹稱為完整二元樹 ( complete binary tree ) 1 2 3 4 5 6 7 8 9 ※ 編號 i 的左兒子編號為 2i + 1，右兒子編號為 2i + 2 ※編號 i 的父節點編號為 (i-1)/2

7 7. 具有n個節點的完整二元樹，其高度為 lg n + 1。
假設完整二元樹的節點數目為 n，高度為 k。 根據二元樹性質(第2點及第3點)，高度為 k 的完整二元樹，節點最多的狀況就是高度為 k 的完滿二元樹，總節點數是2k-1，節點最少的狀況就是高度為 k-1的完滿二元樹再加一個節點，節點數是2k = 2k-1。 k-1 k 節點最少 節點最多 因此： 0 < 2k-1  n  2k-1 0 < 2k-1  n  2k-1 < 2k 0 < 2k-1  n < 2k 取對數 lg (2k-1)  lg n < lg(2k) k-1  lg n < k lg n = k-1 k = lg n + 1 因此：0 < 2k-1  n  2k-1 0 < 2k-1  n  2k-1 < 2k 0 < 2k-1  n < 2k 取對數 lg (2k-1)  lg n < lg(2k) k-1  lg n < k lg n = k-1 k = lg n + 1

8 6-3 二元樹的儲存方式 一維陣列表示法 1. 使用完整二元樹的編號方式。 2. 如果二元樹不很 「完整」，將會有很多儲存空間的浪費。 A
6-3 二元樹的儲存方式 一維陣列表示法 A 1. 使用完整二元樹的編號方式。 B 1 C 2 D 3 E 4 F 5 G 6 H 7 2. 如果二元樹不很 「完整」，將會有很多儲存空間的浪費。 [0] [1] [2] [3] [4] [5] [6] [7] Tree1[] A B C D E F G H A B 1 C 2 D 3 F 6 E 8 G 13 H 14 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] Tree2[] A B C D F E G H

9 鏈結表示法—動態配置節點 typedef struct tagTnode {
struct tagTnode *left_c; // 指向左兒子 char data; //資料 struct tagTnode *right_c; //指向右兒子 }TNode; A B C D E F G H

10 6-4 二元樹的建立 建立二元樹的步驟 讀入資料，如果是 0 則表示停止
6-4 二元樹的建立 建立二元樹的步驟 讀入資料，如果是 0 則表示停止 否則以此資料建立一個節點，並且以同樣原則建立此節點的左子樹，直到不能繼續為止。 接著建立此節點的右子樹，直到不能繼續為止。

11 輸入資料為：ABDH000E00CF00G00，則建立此二元樹的步驟如下：
2.讀入資料 B，建立節點，並為節點 A 的左子節點，接著建立此節點 B 的左子樹 A B 3.讀入資料 D，建立節點，並為節點 B 的左子節點，接著建立此節點 D 的左子樹 A B D 4.讀入資料 H，建立節點，並為節點 D 的左子節點，接著建立此節點 H 的左子樹 A B D H

12 ABDH000E00CF00G00 A B D H 5. 讀入0，表示 H 無左子節點。節點H的左子樹已無法再長，接著建立節點H的右子樹
6. 讀入0，表示 H 無右子節點。節點D的左子樹已無法再長，接著建立節點D的右子樹 7. 讀入0，表示 D 無右子節點。此時節點 B 的左子樹已無法繼續再長 8. 讀入資料 E，以此資料建立節點，並為節點 B 的右子節點 A B D H E

13 ABDH000E00CF00G00 A B D H E 9. 讀入0，表示 E 無左子節點
10. 讀入0，表示 E 無右子節點。節點A的左子樹已無法再長 11. 讀入資料 C，以此資料建立節點，並為節點 A 的右子節點 A B D H E C

14 ABDH000E00CF00G00 12. 讀入資料 F，以此資料建立節點，並為節點 C 的左子節點 A B D H E C F
15. 讀入資料 G，以此資料建立節點，並為節點 C 的右子節點 A B D H E C F G 16. 讀入0，表示 G 無左子節點 17. 讀入0，表示 G 無右子節點。節點 A 的右子樹已無法再長。由於節點 A 是樹根，因此整棵樹也無法繼續再長，建立過程結束

15 6-5 二元樹的走訪 系統性走訪：「前序走訪」、「中序走訪」、和「後序走訪」 前序走訪 ( preorder traverse )：
6-5 二元樹的走訪 系統性走訪：「前序走訪」、「中序走訪」、和「後序走訪」   前序走訪 ( preorder traverse )： l    先拜訪目前的節點 l    再以前序順序拜訪左子樹 l    再以前序順序拜訪右子樹 A B C 前序走訪順序 A B C A B C E D G F J H A B C E D 前序走訪順序 A B D E C A的左子樹 A的右子樹 前序走訪順序 A B D J E C F H G

16 中序走訪 ( inorder traverse )
l    先以中序順序拜訪左子樹 l    再拜訪目前的節點 l    再以中序順序拜訪右子樹 A B C 中序走訪順序 B A C A B C E D A B C E D G F J H 中序走訪順序 D B E A C A的左子樹 A的右子樹 中序走訪順序 J D B E A H F C G

17 後序走訪 ( postorder traverse )：
l    先以後序順序拜訪左子樹 l    再以後序順序拜訪右子樹 l    再拜訪目前的節點 A B C 後序走訪順序 B C A A B C E D A B C E D G F J H 後序走訪順序 D E B C A A的左子樹 A的右子樹 後序走訪順序 J D E B H F G C A

18 前序走訪的順序為：ABDEFCHGI 中序走訪的順序為：DBFEAHCGI 後序走訪的順序為：DFEBHIGCA 例 6.1 A B C E

19 前序走訪函式 中序走訪函式 後序走訪函式 1. void preorder(NODE *p) 2. { if (p != NULL)
3. { visit(p); //拜訪目前的節點 4. preorder(p->left_c); //遞迴拜訪左子樹 5. preorder(p->right_c); //遞迴拜訪右子樹 6. } 7. } 中序走訪函式 1. void inorder(NODE *p) 2. { if (p != NULL) 3. { inorder(p->left_c); //遞迴拜訪左子樹 4. visit(p); //拜訪目前的節點 5. inorder(p->right_c); //遞迴拜訪右子樹 6. } 7. } 後序走訪函式 1. void postorder(NODE *p) 2. { if (p != NULL) 3. { postorder(p->left_c); //遞迴拜訪左子樹 4. postorder(p->right_c); //遞迴拜訪右子樹 5. visit(p); //拜訪目前的節點 6. } 7. }

20 6-6 引線二元樹 ※ n 個節點的二元樹，有 2n – ( n-1 ) = n + 1 個指標是接地的
6-6 引線二元樹 ※ n 個節點的二元樹，有 2n – ( n-1 ) = n + 1 個指標是接地的 ※ 將原本接地的指標作為引線，將左引線指向此節點的中序立即前行者 ，將右引線指向此節點的中序立即後繼者，稱為引線二元樹 A B C D E F G J H I K 如何找節點的中序立即後繼者 ：  1. 如果是右引線，照右引線所指即為後繼者。例如節點K，節點K有右引線，因此照著它的右引線指向節點D，節點D即為節點K的後繼者。  2. 如果是右指標，則先往右，再一路沿著左指標往左，一直到沒有左指標，而是左引線的節點為止。例如節點A，節點A有右指標，則往右到節點C，再一路沿著左指標到達節點H，節點H沒有左指標，而是左引線，因此節點H即為節點A的後繼者。

21 首節點 對整棵樹作中序走訪的過程： A B C D 1 1 E 1 F 1 1 G 1 J 1 H 1 1 I 1 1 K 1
A B C D 1 1 E 1 F 1 1 G 1 J 1 H 1 1 I 1 1 K 1 對整棵樹作中序走訪的過程： 1. 首節點的後繼者，先往右 ( 回到自己 )，再一路往左，可找到節點 J 2. 節點 J 的後繼者，先往右(K)，再一路往左 ( 沒有 )，因此節點 J 的後繼者是節點 K 3. 節點 K 的後繼者，往右是引線，因此節點 K 的後繼者是節點 D 4. ~ 11. 以此類推，順序為：B E A H F C G I 12. 節點 I 的後繼者，往右是引線，因此節點 I 的後繼者是首節點，走訪結束

22 6-7 二元搜尋樹 二元搜尋樹的定義： 對二元搜尋樹中每一個內部節點而言，它的左子樹所有節點的資料值，都小於它的資料值，它的右子樹所有節點的資料值，都大於它的資料值 51 39 70 20 45 63 80 10 42 49 75 ※ 這是一棵二元搜尋樹，因為每個內部節點都符合定義 ※ 對二元搜尋樹作中序走訪，可以得到由小到大排列的順序 ※ 將資料整理成二元搜尋樹，將可以有效率地找到所要的資料

23 二元搜尋樹的建立 每讀入一個資料就依循下列原則，將新節點插入擴充中的二元搜尋樹： 1. 如果是空樹，則新節點為樹根
2. 否則將新節點的資料與樹根相比，小於樹根則往左子樹，大於樹根則往右子樹 3. 重複與此子樹的樹根比較，直到指標接地為止 4. 將新節點加在最後停留之處 我們以下列的資料，示範建立二元搜尋樹的程序： 51、70、39、45 51 70 70加入，70 > 51 ( 樹根 )，往右子樹 51 加入51為樹根 51 39 70 39加入，39 < 51 (樹根 )，往左子樹 51 39 70 45 45加入，45 < 51 (樹根 )，往左子樹。45 > 39，往右子樹。

24 二元搜尋樹的節點搜尋 若搜尋的鍵值為 49 搜尋的過程和插入節點十分類似，依循下列原則：
1. 將搜尋的鍵值 (key) 與樹根相比，若相等則搜尋成功 2. 否則，小於樹根則往左子樹，大於樹根則往右子樹 3. 重複與此子樹的樹根比較，若相等則搜尋成功 4. 若直到指標接地為止都不相等，則搜尋失敗 若搜尋的鍵值為 49 1. 首先鍵值49和樹根資料51相比。49比51小，因此往左子樹，因為根據定義，如果資料49在二元搜尋樹中，只可能在資料51的左子樹中出現 51 2. 鍵值49和資料39相比，49比39大，往右子樹。 39 70 20 45 3. 鍵值49和資料45相比，49比45大，往右子樹 63 80 10 42 4. 鍵值49和資料49相比，相等，搜尋成功 49 75

25 二元搜尋樹的節點刪除 依照要刪除節點所在的位置，分為三種狀況來討論： 狀況1. 要刪除的節點是樹葉：只要直接刪去即可，這是最單純的狀況。
51 51 r r 39 39 p 20 45 45 49 49 狀況2. 要刪除的節點只有一棵子樹（左或右皆同）：只要將其父節點的指標越過欲刪除節點，改指向此節點的子節點即可。 51 51 r r 39 39 p 20 45 30 45 30 49 25 31 49 25 31

26 (1) 找到此節點的「中序立即前行者」，並且以此前行者節點的資料，代替要刪除節點的資料。
狀況 3. 要刪除的節點有二棵子樹，作法是： (1) 找到此節點的「中序立即前行者」，並且以此前行者節點的資料，代替要刪除節點的資料。 (2) 由於此前行者最多只可能有一棵子樹（否則它就不可能被找上），因此再按照前述狀況1或狀況2，直接刪除此前行者即可完成刪除動作。 29 q p s r 35 13 38 6 19 4 10 12 11 (a) 欲刪除 13 29 q p s r 35 12 38 6 19 4 10 11 (b) 由12代替其位 29 p s r 35 12 38 6 19 4 10 11 (c)刪除原來的 12

27 6-8 高度平衡二元樹 (AVL樹) 在AVL樹上，所有內部節點的左子樹高度和右子樹高度，相差小於或等於1。
2 B 1 -1 -1 ( a )AVL樹 ( b )非AVL樹 假設新加入節點為N，而由於新節點的加入，造成原本平衡係數BF為 1的節點其BF變為 2，違反了AVL性質。這時，就必須根據新節點插入的位置，分成四種狀況來旋轉調整，使其恢復AVL性質。 LL型：新節點N插入到節點A的左兒子的左子樹。 RR型：新節點N插入到節點A的右兒子的右子樹。 LR型：新節點N插入到節點A的左兒子的右子樹。 RL型：新節點N插入到節點A的右兒子的左子樹。

28 LL型 插入 20 LL旋轉 A B 1 2 60 A 60 A 41 B 41 70 1 41 B B 70 29 60 A 29 52 29 52 20 52 70 20 N (a)平衡的子樹 (b)失去平衡 (c)重新平衡的子樹 LL旋轉 A B 插入 N 1 A 2 A B B 1 B A AR AR BL BL BR h-1 BL BR BR AR h h-1 h-1 h N N (a)平衡的子樹 (b)失去平衡 (c)重新平衡

29 RR型 RR旋轉 A B 插入 85 -1 60 A -2 60 A 81 B 41 81 B 41 -1 81 B 60 A 93 1
81 B 41 81 B 41 -1 81 B 60 A 93 1 72 93 72 93 1 41 72 85 85 N (a)平衡的子樹 (b)失去平衡 (c)重新平衡的子樹 RR旋轉 A B -1 A 插入 N -2 A B B -1 B A AL AL BR h-1 BL BR BL BR AL BL h h-1 h-1 h N N (a)平衡的子樹 (b)失去平衡 (c)重新平衡

30 LR型 插入 58 LR旋轉 A C 1 70 A 2 70 A 62 C B B 41 75 -1 41 75 -1 41 B -1 70
62 C B B 41 75 -1 41 75 -1 41 B -1 70 A 1 32 62 C 80 32 62 C 80 32 45 68 75 20 45 68 20 45 68 20 58 80 N 58 N (a)平衡的子樹 (b)失去平衡 (c)重新平衡 插入 N LR旋轉 A C 1 A 2 A C B -1 A B AR -1 B AR BL CL CR AR C h C 1 BL BL CL CR CL CR h h-1 N N (a)平衡的子樹 (b)失去平衡 (c)重新平衡

31 RL型 插入 70 RL旋轉 A C -1 42 A -2 42 A 62 C 41 75 41 1 75 B 1 42 A 75 B B
62 C 41 75 41 1 75 B 1 42 A 75 B B 32 62 C 80 32 -1 62 C 80 41 45 68 80 45 68 92 45 68 92 32 70 N 92 70 N (a)平衡的子樹 (b)失去平衡 (c)重新平衡 插入 N RL旋轉 A C -1 A -2 A C B B 1 -1 A B AL BR AL BR C C 1 AL CL CR BR h h CL CR CL CR h-1 N N (a)平衡的子樹 (b)失去平衡 (c)重新平衡

32 6-9 m元搜尋樹及 B 樹 m 階 B 樹符合下列條件： 1. 每個節點至多有 m 個子樹 2. 樹根至少有 2 個子樹，除非它也是樹葉
4. 所有的樹葉都在同一階，亦即從樹根到任一個樹葉所經過的路徑長度均相同 L0 K1 L1 K2 L2 30 60 a 16 22 b 47 c 71 d 4 12 e 18 f 24 27 g 33 40 h 49 i 63 69 j 77 k

33 加入鍵值21 加入鍵值74 B樹鍵值插入的原則，是必須確保插入後仍符合B樹的特性： 經過類似搜尋的過程，找到第一個可插入點（一定是樹葉）。
如果此樹葉的資料欄位有空位，將新鍵值插入適當順序的資料欄位。 如果樹葉的資料欄位已經額滿沒有空位，則樹葉進行節點分裂 (split)，並且分配資料鍵值到兩個樹葉，同時將中間的鍵值（第 m / 2 個）往上插入父節點。 父節點的插入過程如同步驟2和步驟3，如果此節點還需要分裂，則一直重複。因此每次插入最多可能使B樹的高度h增加1。 L0 K1 L1 K2 L2 30 60 a 16 22 b 47 c 71 d 4 12 e 18 21 f 24 27 g 33 40 h 49 i 63 69 j 77 k 加入鍵值74 L0 K1 L1 K2 L2 30 60 a 16 22 b 47 c 71 d 4 12 e 18 21 f 24 27 g 33 40 h 49 i 63 69 j 74 77 k

34 加入鍵值43 L0 K1 L1 K2 L2 30 60 a 16 22 b 47 c 71 d 4 12 e 18 21 f 24 27 g 33 40 h 49 i 63 69 j 74 77 k L0 K1 L1 K2 L2 30 60 a 16 22 b 40 47 c 71 d 4 12 e 18 21 f 24 27 g 33 h 43 h’ 49 i 63 69 j 74 77 k

35 加入鍵值37 L0 K1 L1 K2 L2 30 60 a 16 22 b 40 47 c 71 d 4 12 e 18 21 f 24 27 g 33 37 h 43 h’ 49 i 63 69 j 74 77 k 加入鍵值39 L0 K1 L1 K2 L2 40 x 30 a 60 a’ b c c’ d 16 22 37 47 71 4 12 18 21 24 27 33 39 43 49 63 69 74 77 69

36 6-10 2-3 樹 2 – 3樹的節點鍵值插入，原則如下（與B樹同）： 1. 新鍵值的第一個可插入點一定是樹葉。
樹 2 – 3 樹其實就是「3階的B樹」( B tree of order 3 )。因此在2 – 3樹上的每個節點最多有2個鍵值、3個指標。 具有1個鍵值（2個指標）的節點稱為 “2-node” （2-節點） 具有2個鍵值（3個指標）的節點稱為 ”3-node” （3-節點）。 2 – 3樹的節點結構可以宣告為： 1. typedef struct tagTwo3Node 2. { int KeyLeft, KeyRight ; 3. struct tagTwo3Node *LinkLeft, *LinkMiddle, *LinkRight; 4. } Two3Node; 2 – 3樹的節點結構可以圖示為： LinkLeft KeyLeft LinkMiddle KeyRight LinkRight 2 – 3樹的節點鍵值插入，原則如下（與B樹同）： 1. 新鍵值的第一個可插入點一定是樹葉。 2. 如果樹葉的資料欄位有空位，將鍵值插入適當的資料欄位即告完成。 3. 如果樹葉的資料欄位已經額滿沒有空位，則樹葉進行節點分裂 (split) 。 4. 每次插入最多可能使2 – 3樹的高度h增加1。

37 (1)加入2, 7 (2)加入1 2 c 節點a分裂，鍵值2上提 2 2 7 a 1 a 7 b (3)加入8 (4)加入4 2 7 c 2 c 節點b分裂，鍵值7上提 1 4 8 1 a 7 8 b a b d (5)加入5, 9, 0 2 7 c 1 4 5 8 9 a b d (6)加入3 4 g 節點b分裂，鍵值4上提 節點c分裂，鍵值4上提 2 c 7 f 1 3 5 8 9 a b e d

38 6-11 2-3-4 樹與紅黑樹 2 – 3 – 4樹其實就是「4階的B樹」( B-tree of order 4 )。
樹與紅黑樹 2 – 3 – 4樹其實就是「4階的B樹」( B-tree of order 4 )。 在2 – 3 – 4樹上的每個節點最多有3個鍵值、4個指標。 具有1個鍵值（2個指標）的節點稱為 “2-node” （2-節點） 具有2個鍵值（3個指標）的節點稱為 “3-node” （3-節點） 具有3個鍵值（4個指標）的節點稱為 “4-node” （4-節點）。 2 – 3 – 4樹的節點結構可宣告如下： 1. typedef struct tagTwo34Node 2. { int Key[3]; 3. struct tagTwo34Node *Link[4]; 4. } Two34Node; 2 – 3 – 4樹的節點結構圖示如下： Link[0] Key[0] Link[1] Key[1] Link[2] Key[2] Link[3]

39 每個節點有2個指標，並且每個指標有2種形式：「紅指標」及「黑指標」。在畫出紅－黑樹時，通常以實線表示黑指標，以虛線表示紅指標。
「紅－黑樹」是2 – 3 – 4樹的二元樹表示法。 每個節點有2個指標，並且每個指標有2種形式：「紅指標」及「黑指標」。在畫出紅－黑樹時，通常以實線表示黑指標，以虛線表示紅指標。 2-3-4樹轉成紅黑樹 (1)一個2 – node 轉成1個紅－黑樹節點，2個指標的Color均為Black。 24 a b (2)一個3 – node轉成2個紅－黑樹節點，這2個紅－黑樹節點以1個Red指標連接。 24 27 a b c 或 (3)一個4 – node 轉成3個紅－黑樹節點，中間節點以兩個Red指標連接另2個節點 24 45 27 a b c d

40 此樹的內部路徑長 I = 0 (A)+ 1 (B) + 1 (C) + 2 (D) = 4
6-12 Huffman 樹 內部路徑長 ( internal path length ) ：由樹根到每個內部節點的路徑長度之總和 外部路徑長 (external path length ) ：由樹根到每個外部節點的路徑長度之總和 A B C D E 1 2 3 F 路徑長 G 9 8 7 此樹的內部路徑長 I = 0 (A)+ 1 (B) + 1 (C) + 2 (D) = 4 外部路徑長 E = 2 (E) + 2 (F) + 3 (G) = 7 加權外部路徑長 ：由樹根到每個外部節點的路徑長乘上該節點的加權之總和 此圖的加權外部路徑長 = 2 * 8 (E) + 2 * 7 (F) + 3 * 9 (G) = 57 對具有相同外部節點同時加權也相同的不同二元樹，其加權外部路徑長也不同。其中加權外部路徑長最小的二元樹稱為Huffman樹，或稱最佳二元樹。

41 Huffman演算法 ：由已知的外部節點建構 Huffman 樹（加權外部路徑長最小的樹 ）的過程
開始 演算法：Huffman法建立編碼樹 (編碼字母表與頻率) 將樹葉(字母)按照加權(頻率)由小到大排成一個串列 當串列中多於一個元素，重複迴圈 從串列取出加權最小的兩個子樹生成一個新子樹，其加權為兩個子樹之加權和 將新子樹樹根插入串列適當位置，使串列仍然維持由小到大 迴圈結束 演算法結束 將樹葉按照加權由小到大排成一個串列 是 串列只有一個元素？ 否 取串列左邊兩個加權最小的樹葉生成一個新節點，其加權為兩個樹葉之加權和 將新節點插入串列適當位置，使串列仍然維持由小到大 結束

42 假設有ABCDEF六個樹葉，其加權分別為15, 8, 30, 27, 5, 15
1. 將樹葉按照加權，由小到大排序好，成為一有序串列。   E / 5, B / 8, A / 15, F / 15, D / 27, C / 30 2. 取串列最左邊兩個加權最小的樹葉，作為一新節點N的兩個子節點，新節點N的加權為兩個樹葉的加權之和 N E B 8 13 5 3.  將節點N放入有序串列的適當位置，使串列保持次序。   N / 13, A / 15, F / 15, D / 27, C / 30 4. 取最左邊兩個節點 N 和 A，合成新節點 P P N A 15 28 13 E B 8 5

43 5. 將節點 P 放入有序串列的適當位置，使串列保持次序。 F / 15, D / 27, P / 28, C / 30
6. 取最左邊兩個節點 F 和 D，合成新節點 R P N A 15 28 13 E B 8 5 R F D 27 42 7.  將節點 R 放入有序串列的適當位置，使串列保持次序。   P / 28, C / 30, R / 42 8. 取最左邊兩個節點 P 和 C，合成新節點 S R F D 27 42 15 P N A 28 13 E B 8 5 S C 30 58

44 9. 將節點 S 放入有序串列的適當位置，使串列保持次序。 R / 42, S / 58
10. 取最左邊兩個節點 R 和 S，合成新節點 T，只剩一個節點，停止 A 15 E B 8 5 F D 27 C 30

45 Huffman樹經常用在處理資料的壓縮編碼。假設共有６個字母需要編碼，分別是A/15, B/8, C/30, D/27, E/5, F/15，合起來剛好100 %。我們依照前述 Huffman 演算法建構 Huffman樹： 1 1 1 F 15 D 27 30 C 1 A 15 1 E 5 B 8 A的編碼 = 右左右 = 101 B的編碼 = 右左左右 = 1001 C的編碼 = 右右 = 11 D的編碼 = 左右 = 01 E的編碼 = 右左左左 = 1000 F的編碼 = 左左 = 00

46 編碼一篇1000個字母的文章。根據字母出現的頻率，它們的出現次數分別是：
 A 出現的次數 = 1000 * 15 % = 150 B 出現的次數 = 1000 * 8 % = 80 C 出現的次數 = 1000 * 30 % = 300 D 出現的次數 = 1000 * 27 % = 270 E 出現的次數 = 1000 * 5 % = 50 F 出現的次數 = 1000 * 15 % = 150  因此總共需要的bit數 150 * * * * * * 2 = 2410 未經編碼，每個字母用3個位元表示，( 8 種組合 )，共需3000個位元 2410 壓縮率＝ ( ) * 100 %  20 % 3000