第6章樹和二叉樹-資料下載頁

　　

【正文】 ）中其余樹組成的森林，即 F(R)＝ { T2, T3, … ,Tn}。 樹與森林的遍歷 1. 樹的遍歷 樹的遍歷方法主要有以下兩種： （ 1）先根遍歷 若樹非空，則遍歷方法為： ①訪問根結點。 ②從左到右，依次 先根遍歷根結點的每一棵子樹。 A B E C D F G H 如圖中樹的先根遍歷序列為： ABECFHGD。 (2)后根遍歷 若樹非空，則遍歷方法為： ① 從左到右，依次后根遍歷根結點的每一棵子樹。 ②訪問根結點。 如圖中樹的后根遍歷序列為： EBHFGCDA。 樹的遍歷結果與由樹轉化成的二叉樹有如下對應關系： 樹的先根遍歷 轉化二叉樹的前序遍歷 樹的后根遍歷 轉化二叉樹的中序遍歷 void RootFirst(CSTree root) { if (root!=NULL) { Visit(root data)。 /* 訪問根結點 */ p= root FirstChild。 while (p!=NULL) { RootFirst( p )。 /* 訪問以 p為根的子樹 */ p = p Nextsibling。 } } } 方法一 void RootFirst(CSTree root) { if (root!=NULL) { Visit (root data)。 /*訪問根結點 */ RootFirst (rootFirstChild)。 /*先根遍歷首子樹 */ RootFirst (rootNextsibling)。 /*先根遍歷兄弟樹 */ } } 方法二 3. 森林的遍歷 森林的遍歷方法主要有以下三種： (1)先序遍歷 若森林非空，則遍歷方法為： ① 訪問森林中第一棵樹的根結點。 ②先序遍歷第一棵樹的根結點的子樹森林。 ③先序遍歷除去第一棵樹之后剩余的樹構成的森林。 (2)中序遍歷 若森林非空，則遍歷方法為： ① 中序 遍歷森林中第一棵樹的根結點的子樹森林。 ②訪問 第一棵樹的根結點。 ③中序 遍歷除去第一棵樹之后剩余的樹構成的森林。 (3)后序遍歷 若森林非空，則遍歷方法為： ① 后序 遍歷森林中第一棵樹的根結點的子樹森林。 ②后序 遍歷除去第一棵樹之后剩余的樹構成的森林。 ③訪問第一棵樹的根結點。 哈夫曼樹及其應用 哈夫曼樹 哈夫曼編碼 1. 哈夫曼樹的 基本概念： 路徑 ：指從一個結點到另一個結點之間的分支序列。 路徑長度 ：指從一個結點到另一個結點所經過的分支數目。 結點的權 ：給樹的每個結點賦予一個具有某種實際意義的實數，我們稱該實數為這個 結點的權 。 帶權路徑長度 ：在樹形結構中，我們把從樹根到某一結點的路徑長度與該結點的權的乘積，叫做該結點的 帶權路徑長度 。 樹的帶權路徑長度 ：為樹中所有葉子結點的帶權路徑長度之和，通常記為： 其中 n為葉子結點的個數， wi為第 i個葉子結點的權值， li為第 i個葉子結點的路徑長度。 WPL=?wi li i=1 n 例如下圖所示的具有不同帶權路徑長度的二叉樹 WPL(a)=7 2＋ 5 2＋ 2 2＋ 4 2＝ 36 WPL(b)=4 2＋ 7 3＋ 5 3＋ 2 1＝ 46 WPL(c)=7 1＋ 5 2＋ 2 3＋ 4 3＝ 35 A B C D 7 5 2 4 (a)權為 36 C B D A 7 5 2 4 (b)權為 46 A B C D 7 5 2 4 (c)權為 35 問題 1：什么樣的二叉樹的路徑長度 PL最?。? 一棵樹的路徑長度為 0結點至多只有 1個 （ 根 ） ； 路徑長度為 1結點至多只有 2個 （ 兩個孩子 ） ； 路徑長度為 2結點至多只有 4個； 依此類推：路徑長度為 K結點至多只有 2k個 ， 所以 n個結點二叉樹其路徑長度至少等于如下序列的前 n項之和 。 路徑長度 0 ， 1 ， 1 ， 2， 2， 2， 2， 3， 3， 3， 3， 3， 3， 3， 3， 4， 4， ... 結點數 n n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 ... K=15 由此可知，結點 n對應的路徑長度為 ? log2n ?，所以前 n項之和為 : n k=1 ? ? log2k ? 完全二叉樹的路徑長度為： 20 0+21 1+22 2+? + 2h h= h k=1 ? ? log2k ? h為樹的深度，其路徑長度可達到 最小 ，所以 完全二叉樹具有最小路徑長度的性質，但不具有唯一性 。 例如：下列不同形狀的二叉樹具有最小的路徑長度 A B C D E PL=0+1+1+2+2=6 A B D C E PL=0+1+1+2+2=6 問題 2：什么樣的帶權樹路徑長度最??？ 例如：給定一個權值序列 {2,3,4,7}，可構造的多種二叉樹的形態。 (a) WPL=2 2＋ 2 3+2 4+2 7=32 2 3 4 7 4 2 3 7 (b) WPL=1 2＋ 2 3+3 4+3 7=41 3 7 4 2 (c) WPL=1 7＋ 2 4+3 3+3 2=30 2. 構造哈夫曼樹 哈夫曼樹 又叫 最優二叉樹 ，它是由 n個帶權葉子結點構成的所有二叉樹中 帶權路徑長度 WPL最短 的二叉樹。 構造哈夫曼算法的步驟如下： (1)用給定的 n個權值 {w1,w2, … ,wn}對應的 n個結點構成 n棵二叉樹的森林F={T1,T2, … ,Tn}，其中每一棵二叉樹 Ti (1≤i≤n) 都只有一個權值為 wi的根結點，其左、右子樹為空。 (2)在森林 F中選擇兩棵根結點權值最小的二叉樹，作為一棵新二叉樹的左、右子樹，標記新二叉樹的根結點權值為其左右子樹的根結點權值之和。 (3)從 F中刪除被選中的那兩棵二叉樹，同時把新構成的二叉樹加入到森林F中。 (4)重復（ 2）、（ 3）操作，直到森林中只含有一棵二叉樹為止，此時得到的這棵二叉樹就是哈夫曼樹。 直觀地看，在哈夫曼樹中權越大的葉子離根越近，則其具有最小帶權路徑長度。 哈夫曼樹的手工構造的方法也非常簡單： 給定 數列 {W1....Wn}，以 n個權值構成 n棵樹的森林 F；將 F={T1....Tn}按權從小到大排列； 取 T1和 T2合并組成一棵樹，使其根結點的權值 T=T1+T2，再按大小插入 F，反復此過程直到只有一棵樹為止。 (1)存儲結構 哈夫曼樹是一種二叉樹 ,由于哈夫曼樹中沒有度為 1的結點，則一棵有n個葉子的哈夫曼樹共有 2 n－ 1個結點，可以用一個大小為 2 n－ 1 的一維數組存放哈夫曼樹的各個結點。由于每個結點同時還包含其雙親信息和孩子結點的信息，所以構成一個靜態三叉鏈表。 靜態三叉鏈表中：每個結點的結構為 : 權值 雙親序號 左孩子序號 右孩子序號 各結點存儲在一維數組中， 0號單元不使用，從 1號位置開始使用。 A B C E D data parent LChild RChild 1 A 0 2 3 2 B 1 0 0 3 C 1 4 5 4 D 3 0 0 5 E 3 0 0 (2)哈夫曼樹的類型定義 用靜態三叉鏈表實現的哈夫曼樹類型定義如下： define N 20 /* 葉子結點的最大值 。 */ define M 2*N1 /* 所有結點的最大值 */ typedef struct { int weight 。 /* 結點的權值 */ int parent 。 /* 雙親的下標 */ int LChild 。 /* 左孩子結點的下標 */ int RChild 。 /* 右孩子結點的下標 */ } HTNode, HuffmanTree[M+1]。 /* HuffmanTree是一個結構數組類型， 0號單元不用。 */ 4. 哈夫曼樹的算法實現 【 算法描述 】 void CrtHuffmanTree(HuffmanTree ht, int w[ ], int n) { /*構造哈夫曼樹 ht[M+1]， w[ ]存放 n個權值 。 */ for(i=1。i=n。i++) ht[i] ={ w[i],0,0,0}。 /* 1 ~ n號單元存放葉子結點 ， 初始化 */ m=2*n1。 for(i=n+1。i=m。i++) ht[i] ={0,0,0,0}。 /*————————————初始化完畢 ！ 對應算法步驟 1—————————*/ for(i=n+1。 i=m。 i++) /*創建非葉結點 ， 建哈夫曼樹 */ { select(ht, i1, s1, s2)。 /* 在 ht[1] ~ ht[i1] 的范圍內選擇兩個 parent為 0且 weight最小的結點 ， 其序號分別賦值給 s s2返回 */ ht [i].weight= ht [s1].weight+ ht [s2].weight。 ht [s1].parent=i。 ht [s2].parent=i。 ht [i].LChild=s1。 ht [i].RChild=s2。 } /*哈夫曼樹建立完畢 */ } 例：傳送數據中的二進制編碼。要傳送數據 state,seat,act,tea,cat,set,a,eat，如何使傳送的長度最短？ 為了保證長度最短，先計算各個字符出現的次數，然后將出現次數當作權。 0 1 字符 s t a e c 字符出現的次數 3 8 7 5 2 按權構造哈夫曼樹的過程 如下圖： 按照創建哈夫曼樹的算法，對上圖建立哈夫曼樹的結果如下表： 哈夫曼編碼 哈夫曼樹最典型的應用是在編碼技術上的應用。利用哈夫曼樹，我們可以得到平均長度最短的編碼。 例如：設有一臺模型機，共有 7種不同的指令，其使用頻率為： 指 令 I1 I2 I3 I4 I5 I6 I7 編 碼 0 1 00 01 000 001 010 指 令 I1 I2 I3 I4 I5 I6 I7 使用頻率（ pi） 變長編碼為： (1)前綴碼： 如果在一個編碼系統中，任一個編碼都不是其他任何編碼的前綴（最左子串），則稱該編碼系統中的編碼是前綴碼。例如，一組編碼 01， 001， 010， 100， 110就不是前綴碼，因為 01是 010的前綴，若去掉 01或 010就是前綴碼。例如，名字中的鄭霞、鄭霞錦就不是前綴碼。 (2)哈夫曼編碼： 對一棵具有 n個葉子的哈夫曼樹，若對樹中的每個左分支賦予 0，右分支賦予 1，則從根到每個葉子的通路上，各分支的賦值分別構成一個二進制串，該二進制串就稱為哈夫曼編碼。 定理 61 哈夫曼編碼是前綴碼。 證明：哈夫曼編碼是根到葉子路徑上的邊的編碼的序列，也就是等價邊序列，而由樹的特點知，若路徑 A是另一條路經 B的最左部分，則 B經過了 A，因此， A的終點不是葉子。而哈夫曼編碼都對應終點為葉子的路徑，所以，任一哈夫曼碼都不會與任意其他哈夫曼編碼的前部分完全重疊，因此哈夫曼編碼是前綴碼。 定理 62 哈夫曼編碼是最優前綴碼。 即對于 n個字符，分別以它們的使用頻度為葉子權，構造哈夫曼樹，則該樹對應的哈夫曼編碼，能使各種報文（由這 n種字符構成的文本）對應的二進制串的平均長度最短。 證明： 由于哈夫曼編碼對應葉權為各字符使用頻度的哈夫曼樹，因此，該樹為帶權長度最小的樹，即 最小，其中Wi是第 i個字符的使用頻度，而 Pi是第 i個字符的編碼長度，這正是度量報文的平均長度的式子