【正文】 7. 了解 最優(yōu)樹(shù)的特性 ，掌握 建立最優(yōu)樹(shù)和赫夫曼編碼 的方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng) 掌握 1 至 2 種 建立 二叉樹(shù)和樹(shù)的 存儲(chǔ)結(jié)構(gòu)的方法 。二叉樹(shù)的 線索化過(guò)程是 基于 對(duì)二叉樹(shù)進(jìn)行 遍歷 ，而線索二叉樹(shù)上的 線索又為相應(yīng)的遍歷提供 了 方便 。 層次遍歷 是按另一種搜索策略進(jìn)行的遍歷。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。 2. 熟悉二叉樹(shù)的各種 存儲(chǔ)結(jié)構(gòu) 的特點(diǎn)及適用范圍。cd[start])； } free(cd)。 HC[i]=(char * )malloc((nstart)*sizeof(char))。c=f,f=HT[f].parent if(HT[f].lchild==c cd[start]=“0”。i++){ start=n1； for(c=i,f=HT[i].parent。 cd[n1]=“\0”； for(i=1。 HT[s2].parent=i； //填寫雙親結(jié)點(diǎn)編號(hào) HTIi].1child=s1； HT[j].rchild=s2； HT[i].weight=T[s1].weight+T[s2].weight； } // end for //從葉子到根逆向求每個(gè)字符的赫夫曼編碼 HC=(Huffmancode)malloc((n+1)*sizeof(char *))。i=m。i=n。 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))。HC /*HF編碼表 */, int *w /*各字符的權(quán)值 數(shù)組 */,){ if(n=1) return。 //動(dòng)態(tài)分配數(shù)組存儲(chǔ) 赫夫曼編碼表 第二節(jié) 赫夫曼編碼 Weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 29 7 8 14 23 3 11 0 1 2 3 4 5 6 7 W 5 29 8 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 23 3 11 9991 78 10 10 3 415 11 11 12 819 14 14 12 13 13 15 15 529 42 58 100 210 11 614 12 13 HC 0 cd 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 0 1 1 ↑ start 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 求赫夫曼編碼過(guò)程的實(shí)例 : HT數(shù)組 求哈夫曼編碼的算法 : void HuffmanCoding(HuffmanTree amp。//動(dòng)態(tài)分配數(shù)組存儲(chǔ) 樹(shù) Typedef char **Huffmancode。 赫夫曼編碼的構(gòu)造方法 ： 第二節(jié) 赫夫曼編碼 例如 ： 假設(shè)有一個(gè)電文字符集中有 8個(gè)字符，每個(gè)字符 的使用頻率分別為 {, ,}， 現(xiàn)以此為例設(shè)計(jì)赫夫曼編碼。稱為赫夫曼編碼。 但隨之帶來(lái)了一個(gè)問(wèn)題，接收方接到這段電文后無(wú) 法進(jìn)行譯碼，因?yàn)闊o(wú)法斷定前面 4個(gè) 0是 4個(gè) A， 1個(gè) B加 2個(gè) A，還是 2個(gè) B，即譯碼不唯一，因此這種編碼方法 不可使用。 ?使用頻度較 高 的字符分配一個(gè)相對(duì)比較 短 的編碼， ?使用頻度較 低 的字符分配一個(gè)比較 長(zhǎng) 的編碼。 這種編碼的特點(diǎn) : 譯碼簡(jiǎn)單且具有唯一性，但編碼長(zhǎng)度并不是最短的。若現(xiàn)在電文為：ABACCDA，則應(yīng)發(fā)送二進(jìn)制序列： 00010010101100，總長(zhǎng)度為 14位。 第二節(jié) 赫夫曼編碼 等長(zhǎng)編碼：每個(gè)字符的編碼 長(zhǎng)度相同 。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則： （ 1）發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后必須具有 唯一性 ，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣； （ 2）發(fā)送的二進(jìn)制編碼 盡可能地短 。 這棵樹(shù)便是赫夫曼樹(shù) 。 ? (3) 在 F中刪除這兩棵樹(shù) ,同時(shí)將新得到的二叉樹(shù)加入 F中 。 k=1 第一節(jié) 赫夫曼樹(shù)及其應(yīng)用 a b c d 7 5 2 4 WPL=7x3+5x3+2x1+4x2 = 46 例：下面兩棵二叉樹(shù)的四個(gè)葉子結(jié)點(diǎn) a,b,c,d的權(quán)值為 4 c d a b 7 5 2 4 (a)WPL=7x2+5x2+2x2+4x2 = 36 (b)WPL=7x1+5x2+2x2+4x2 = 35 第一節(jié) 赫夫曼樹(shù)及其應(yīng)用 a b c d 7 5 2 4 最優(yōu)二叉樹(shù)的定義 ? 假設(shè)有 n個(gè)權(quán)值 {ω 1, ω 2, … , ω n}， 試構(gòu)造一棵有 n個(gè)葉子結(jié)點(diǎn) 的二叉樹(shù) ， 每個(gè)葉子結(jié)點(diǎn)帶權(quán)為 ω i, 則其中： 帶權(quán)路徑長(zhǎng)度 WPL最小的二叉樹(shù)稱做最優(yōu)二叉樹(shù) ， 或赫夫曼樹(shù) 第一節(jié) 赫夫曼樹(shù)及其應(yīng)用 例下面三棵二叉樹(shù)的四個(gè)葉子結(jié)點(diǎn) a,b,c,d的權(quán)值為 4 a b c d 7 5 2 4 a b c d 7 5 2 4 c d a b 7 5 2 4 (a)WPL=7x2+5x2+2x2+4x2 = 36 (b)WPL=7x3+5x3+2x1+4x2 = 46 (c)WPL=7x1+5x2+2x2+4x2 = 35 第一節(jié) 赫夫曼樹(shù)及其應(yīng)用 (a)WPL=10x4+30x4+40x3+15x2+5x1=315 10 中 90 差 及格 5 15 40 良 優(yōu) 30 60 70 80 N N N N Y Y Y Y 10 70 90 差 中 5 40 15 良 優(yōu) 30 60 及格 80 N N N N Y Y Y Y 第一節(jié) 赫夫曼樹(shù)及其應(yīng)用 (b)WPL=5x3+15x3+40x2+30x2+10x2=220 構(gòu)造赫夫曼樹(shù)的算法思想 ? (1) 根據(jù)給定的 n個(gè)權(quán)值 {w1,w2, … ,wn}構(gòu)成 n棵二叉樹(shù)的集合 F={T1,T2, … ,Tn}， 其中每棵二叉樹(shù) Ti中只有一個(gè)帶權(quán)為 Wi的根結(jié)點(diǎn) ,其左右子樹(shù)均空 。 ? 樹(shù)的路徑長(zhǎng)度 : 樹(shù)的路徑長(zhǎng)度是從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和 。 二、中序遍歷森林： 若森林非空，則 （ 1）中序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林； （ 2）訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)； （ 3）中序遍歷除去第一棵樹(shù)之后的森林。 R A D E B C F G H K 二、后根遍歷： （ 1）依次后根遍歷每棵子樹(shù)。={T2,T3, … ，Tm}是由 B的右子樹(shù) RB轉(zhuǎn)換而成的森林 。={T2,T3, … ,Tm} 轉(zhuǎn)換而成的二叉樹(shù) . 第二節(jié) 森林與二叉樹(shù)的轉(zhuǎn)換 二、 二叉樹(shù)轉(zhuǎn)換成森林 ? 如果 B=(root,LB,RB)是一棵二叉樹(shù) ,則可按如下規(guī)則轉(zhuǎn)換成森林 F={T1,T2, … ,Tm}： ? (1)若 B為空 ， 則 F為空； ? (2)若 B非空 ， 則 F中第一棵樹(shù) T1的根 ROOT(T1)即為二叉樹(shù) B的根 root； ? T1中的根結(jié)點(diǎn)的子樹(shù)森林 F1是由 B的左子樹(shù)LB轉(zhuǎn)換而成的森林 。 ? (1)若 F為空 ， 即 m=0,則 B為空樹(shù)； ? (2)若 F非空 ， 即 m0， 則 B的根 root即為森林中第一棵樹(shù)的根 ROOT(T1)； ? B的左子樹(shù) LB是從 T1中根結(jié)點(diǎn)的子樹(shù)森林F1={T11,T12, … ,T1m1}轉(zhuǎn)換而成的二叉樹(shù) 。 }CSNode, *CSTree。 第一節(jié) 樹(shù)的存儲(chǔ)結(jié)構(gòu) 三、孩子兄弟表示法 樹(shù)的二叉樹(shù)表示法 (二叉鏈表示法 ) ? //樹(shù)的二叉鏈表 (孩子兄弟 )存儲(chǔ)表示 typedef struct CSNode { ELemType data。 int n, r。 //孩子鏈表頭指針 }CTBox。 typedef struct { TElemType data。 struct CTNode *next。 = 0。 R A B / C D / E / F G / H / K / 1 2 3 / 4 5 / 6 / 7 8 9 / [ ]。 //結(jié)點(diǎn)數(shù) }PTree。 typedef struct{ PTNode nodes[MAX_TREE_SIZE]。 //第 2個(gè)孩子 位置域 ...... int childd。 int child1。 第一節(jié) 樹(shù)的存儲(chǔ)結(jié)構(gòu) R A D E F C B G K H 0 1 2 3 4 5 6 7 8 9 數(shù)組下標(biāo) : * 便于涉及孩子的操作；求雙親不方便； * 采用同構(gòu)的結(jié)點(diǎn)，空間浪費(fèi)。