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