【正文】 序遍歷其余的樹所構(gòu)成的森林； 二、 樹與森林的遍歷 先序遍歷森林 D H I J G A C F B E B E A C F D G H I J 先序遍歷序列： 二、 樹與森林的遍歷 先序遍歷 : ?訪問第一棵樹的根 。 ?先序遍歷第一棵樹中的根 結(jié)點(diǎn)的子樹森林； ?先序遍歷其余的樹所構(gòu)成 的森林； A B C D E F G H I J 中序遍歷序列： BCDAFEHJIG 中序遍歷森林 二、 樹與森林的遍歷 中序遍歷 : ?中序遍歷第一棵樹的子樹； ?訪問第一棵樹的根 。 ?中序遍歷其余的樹所構(gòu)成的 森林； 三、 森林與二叉樹的轉(zhuǎn)換 在森林與二叉樹 之間存在一一對(duì)應(yīng)的關(guān)系。 1). 森林 =二叉樹的轉(zhuǎn)換 自然轉(zhuǎn)換法： 凡是 兄弟 用線連起來，然后去掉雙親到子女的連線， 但保留雙親到其第一子女的連線，最后轉(zhuǎn) 45176。 例： 森林到二叉樹的轉(zhuǎn)換 A B C D E F G H I J A B C D E F G H I J 前序序列： ABCDEFGHIJ 前序序列： ABCDEFGHIJ = 三、 森林與二叉樹的轉(zhuǎn)換 中序序列： BCDAFEHJIG 中序序列： BCDAFEHJIG = 2) 二叉樹 =森林的轉(zhuǎn)換 自然轉(zhuǎn)換法： 若某結(jié)點(diǎn)是其雙親的左孩子，則該結(jié)點(diǎn)的右孩子、 右孩子的右孩子 …, 都與該結(jié)點(diǎn)的雙親連接起來 , 最后去掉所有雙親到右孩子的連線 . 三、 森林與二叉樹的轉(zhuǎn)換 A B C D E F G H I J A B C D E F G H I J 問題提出 :在 數(shù)據(jù)通信中，用二進(jìn)制給每個(gè)字 符編碼 ,如何使電文總長(zhǎng)最短且不產(chǎn)生二義性 ? 根據(jù)字符出現(xiàn)頻率，利用 Huffman樹可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的 Huffman編碼是一種最優(yōu)前綴編碼 ， 即使所傳電文的總長(zhǎng)度最短。 任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。 Huffman樹及其應(yīng)用 Huffman樹及其應(yīng)用 ?最優(yōu)二叉樹（ Huffman） ?如何構(gòu)造最優(yōu)二叉樹 ?如何求哈夫曼編碼 一、哈夫曼樹 (最優(yōu)樹 )的定義 結(jié)點(diǎn)的路徑長(zhǎng)度 ： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的 數(shù)目。 樹的路徑長(zhǎng)度 ：樹中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。 (結(jié)點(diǎn) )帶權(quán)路徑長(zhǎng)度 :結(jié)點(diǎn)的路徑長(zhǎng)度 *結(jié)點(diǎn)的權(quán) =li*wi 樹的帶權(quán)路徑長(zhǎng)度 ：樹中所有 葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度 之和 WPL(T)= ??nkkklw1設(shè) K={k1,k2,… kn},它們的權(quán) W={w1,w2,… ,wn}, 構(gòu)造以 k1,k2,… kn為葉結(jié)點(diǎn)的二叉樹，使得 WPL= 為最小 ,則稱之為 “ 最優(yōu)二叉樹 ”。 一、哈夫曼樹 (最優(yōu)樹 )的定義 ??nkkklw1例 W={1,2,4,6} ,可構(gòu)造出如下的二叉樹： 1 2 4 6 1 2 4 6 6 4 1 2 WPL =(1+2+4+6)*2=26 WPL =1+2*2+(4+6)*3=35 WPL =6+4*2+(1+2)*3=23 (1) (2) (3) 根據(jù)定義求 Huffman樹的方法是： 對(duì)給定的 n個(gè)葉子結(jié)點(diǎn)（外部結(jié)點(diǎn)），構(gòu)造出全部二叉樹并求出其 WPL， 然后找出 WPL最小的樹。 當(dāng) n較大時(shí)，顯然這種方法是不可取的。 二、構(gòu)造 huffman樹 算法思想： 1. 根據(jù)權(quán)值 {w1 , w2 ,…, w n}構(gòu)造 n個(gè)二叉樹 F={T1 , T2 , …, T n}， 其中 Ti中是只含權(quán)值為 wi 的結(jié)點(diǎn)。 2. 從 F中選兩個(gè)權(quán)值最小的二叉樹 Ti和 Tj， 構(gòu)造一個(gè) 根結(jié)點(diǎn) R, R的權(quán) wR為 wi + wj 。 3. 從 F中刪除 Ti和 Tj ， 加入新的樹 R到 F中。 4. 重復(fù) 2， 3 直到 F中只有一棵樹 (或執(zhí)行 n1次 )為止。 問題 : 如何證明所構(gòu)造的二叉樹是最優(yōu)樹 ? 例 : 已知權(quán)值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 6 7 3 8 5 9 例 : 已知權(quán)值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 3 8 5 7 6 13 9 例 : 已知權(quán)值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 7 6 13 3 8 5 9 17 例 : 已知權(quán)值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 3 8 5 9 17 7 6 13 30 用 n個(gè)葉結(jié)點(diǎn)構(gòu)造出的最優(yōu)二叉樹共有幾個(gè)結(jié)點(diǎn)？ ?構(gòu)造最優(yōu)樹時(shí)共執(zhí)行 n1次循環(huán)，每次增加一個(gè)新 結(jié)點(diǎn)，共增加了 n1個(gè)結(jié)點(diǎn)，所以結(jié)點(diǎn)總數(shù)一定 是 n+n1=2n1 ?因?yàn)?n0=n2+1, 所以 n2=n01, 又由于在 最優(yōu)二叉樹中 沒有度為 1的結(jié)點(diǎn) ,所以在最優(yōu)二叉樹中總的結(jié)點(diǎn)數(shù)為 n+n1=2n1 Huffman 算法的實(shí)現(xiàn)： Huffman編碼： 設(shè)字符集為 {c1 , c2 ,…, c n} , 看作葉結(jié)點(diǎn) 出現(xiàn)概率為 {w1 , w2 ,…, w n} ,葉結(jié)點(diǎn)的權(quán) （ 1）構(gòu)造 Huffman樹 （ 2）左分支標(biāo) 0，右分支標(biāo) 1 （ 3）根到葉結(jié)點(diǎn) ci的路徑上的二進(jìn)制編碼就是 ci的編碼 編碼長(zhǎng)度為 { l1 , l2 ,…, l n} 是葉結(jié)點(diǎn)的路徑長(zhǎng)度 , 則 樹的帶權(quán)路徑長(zhǎng)度 WPL是： ???nkkk lwW P L1 根 到任何 ci的路徑都不會(huì)經(jīng)過任何其它 ck, 因此 Huffman編碼是 無前綴編碼 ，即任何一個(gè)編碼都不 會(huì)是另一個(gè)編碼的前綴。 例： 字符集 {a,b,c,d,e,f,g,h}出現(xiàn) 概率 分別是 {, , , , , , , } Huffman編碼： (1) 構(gòu)造 Huffman 樹： a b c h d e f g 100 42 58 19 29 15 8 23 3 5 11 29 14 7 8 0 1 1 1 1 1 1 1 0 0 0 0 0 0 (2)編碼： a: 110 b: 1111 c: 011 d: 00 e: 10 f: 0101 g: 0100 h: 1110 (3)編碼長(zhǎng)度： WPL= 2*+4*+ 4*+ 3*+ 2*+3*+4*+4*= 0 0 0 0 0 1 1 1 1 1 1 Huffman 算法的實(shí)現(xiàn)： 用數(shù)組存儲(chǔ) Huffman 樹，每個(gè)數(shù)組元素 HTNode包括 4個(gè)域 : 1 2 3 n n+1 2n1 權(quán) w 雙親 parent 左子女 lchild 右子女 rchild 葉子結(jié)點(diǎn) (外部結(jié)點(diǎn) ) 內(nèi)部結(jié)點(diǎn) //——哈夫曼樹和哈夫曼編碼的存儲(chǔ)表示 —— typedef struct{ unsigned int weight； unsigned int parent， lchild， rchild； }HTNode， *HuffmanTree； //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹 typedef char **HuffmanCode； //動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表 構(gòu)造哈夫曼樹的算法 void HuffmanCoding(HuffmanTree amp。HT， HuffmanCode amp。Hc,int *w,int n) { //w存放 n個(gè)字符的權(quán)值 (均 0),構(gòu)造哈夫曼樹 ,并求出 n個(gè)字符的赫夫曼編碼 Hc。 if(n=1) return； m=2*n1。 HT=(HuffmanTree)malloc((m十 1)*sizeof(HTNode))； // 0號(hào)單元未用 for(p=HT+1, i=1。 i=n。 ++i, ++p,++w) *p= {*w， 0， 0， 0 }； //前 n個(gè)結(jié)點(diǎn) for(。 i=m； ++i， ++p) *p={0， 0， 0， 0}； //后 n1個(gè)結(jié)點(diǎn) for(i=n+1； i=m； ++i){ //建哈夫曼樹 //在 HT[1..i1]選擇 parent為 0且 weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為 s1和 s2。 Select(HT， i1， s1， s2)； HT[s1].parent=HT[s2].parent=i。 HT[i].lchild=s1。 HT[i].rchild=s2； HT[i].weight=HT[s1].weight+HT[s2].weight； } //—從葉子到根逆向求每個(gè)字符的哈夫曼編碼 — HC=(HuffmanCode)malloc((n十 1)*sizeof(char*))。 //分配 n個(gè)字符編碼的頭指針向量 cd=(char*)malloc(n*sizeof(char))； //分配求編碼的工作空間 cd[n1]=＼ 0。； //編碼結(jié)束符。 for(i=1。i=n； ++i){ //逐個(gè)字符求哈夫曼編碼 start=n1； //編碼結(jié)束符位置 for(c=i， f=HT[i].parent； f!=0； c=f， f=HT[f].parent) //從葉子到根逆向求編碼 if(HT[f].lchild==c) cd[start]=0； else cd[start]=1； HC[i]=(char*)malloc((n—start)*sizeof(char))； //為第 i個(gè)字符編碼分配空間 strcpy(Hc[i]， amp。cd[start])； //從 cd復(fù)制編碼 (串 )到 Hc } free(cd)； //釋放工作空間 } //HuffanCoding 定義和性質(zhì) 存儲(chǔ)結(jié)構(gòu) 遍歷 線索化：線索樹 順序結(jié)構(gòu) 鏈?zhǔn)浇Y(jié)構(gòu) 二叉鏈表 三叉鏈表 先序線索樹 中序線索樹 后序線索樹 樹 二叉樹 森林 先 序 遍 歷 中 序 遍 歷 遍歷 存儲(chǔ)結(jié)構(gòu) 遍歷 雙親表示 孩子表示 孩子兄弟 先序遍歷 后序遍歷 中序遍歷 后序遍歷 先序遍歷 Huffman樹 定義 ,構(gòu)造 ,編碼 本章小結(jié) ?理解樹形結(jié)構(gòu)的基本概念和術(shù)語； ?深刻領(lǐng)會(huì) 二叉樹的定義和存儲(chǔ)結(jié)構(gòu)，熟悉二叉樹的 遍歷并熟練掌握遍歷算法 ； ?理解二叉樹線索化的實(shí)質(zhì)，熟練掌握二叉樹的線索 化過程以及遍歷中序線索二叉樹的方法 。 ?理解樹和森林的定義、樹的存儲(chǔ)結(jié)構(gòu)并掌握樹、森 林與二叉樹之間的相互轉(zhuǎn)換方法。 ?理解最優(yōu)樹的特性，掌握建立最優(yōu)樹和 Huffman編 碼的方法 。在此基礎(chǔ)上能進(jìn)行算法設(shè)計(jì)。 本章小結(jié) 作 業(yè) 書面作業(yè) : p38: ， p39: p40: p41: p43: 上機(jī)作業(yè) : (使用棧非遞歸實(shí)現(xiàn)，三種遍歷任選一種，前序中序滿分 4分，后序滿分 5分 ) 2. 哈夫曼編 /譯碼器 (p149)