【正文】 +4x2 = 36 (b)WPL=7x3+5x3+2x1+4x2 = 46 (c)WPL=7x1+5x2+2x2+4x2 = 35 第一節(jié) 赫夫曼樹及其應(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é) 赫夫曼樹及其應(yīng)用 (b)WPL=5x3+15x3+40x2+30x2+10x2=220 構(gòu)造赫夫曼樹的算法思想 ? (1) 根據(jù)給定的 n個權(quán)值 {w1,w2, … ,wn}構(gòu)成 n棵二叉樹的集合 F={T1,T2, … ,Tn}， 其中每棵二叉樹 Ti中只有一個帶權(quán)為 Wi的根結(jié)點 ,其左右子樹均空 。 這棵樹便是赫夫曼樹 。 第二節(jié) 赫夫曼編碼 等長編碼：每個字符的編碼 長度相同 。 這種編碼的特點 : 譯碼簡單且具有唯一性，但編碼長度并不是最短的。 但隨之帶來了一個問題，接收方接到這段電文后無 法進行譯碼，因為無法斷定前面 4個 0是 4個 A， 1個 B加 2個 A，還是 2個 B，即譯碼不唯一，因此這種編碼方法 不可使用。 赫夫曼編碼的構(gòu)造方法 ： 第二節(jié) 赫夫曼編碼 例如 ： 假設(shè)有一個電文字符集中有 8個字符，每個字符 的使用頻率分別為 {, ,}， 現(xiàn)以此為例設(shè)計赫夫曼編碼。 //動態(tài)分配數(shù)組存儲 赫夫曼編碼表 第二節(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 求赫夫曼編碼過程的實例 : HT數(shù)組 求哈夫曼編碼的算法 : void HuffmanCoding(HuffmanTree amp。 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))。i=m。 cd[n1]=“\0”； for(i=1。c=f,f=HT[f].parent if(HT[f].lchild==c cd[start]=“0”。cd[start])； } free(cd)。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結(jié)構(gòu)有關(guān)。二叉樹的 線索化過程是 基于 對二叉樹進行 遍歷 ，而線索二叉樹上的 線索又為相應(yīng)的遍歷提供 了 方便 。 7. 了解 最優(yōu)樹的特性 ，掌握 建立最優(yōu)樹和赫夫曼編碼 的方法。建立存儲結(jié)構(gòu)是進行其它操作的前提，因此讀者應(yīng) 掌握 1 至 2 種 建立 二叉樹和樹的 存儲結(jié)構(gòu)的方法 。 層次遍歷 是按另一種搜索策略進行的遍歷。 2. 熟悉二叉樹的各種 存儲結(jié)構(gòu) 的特點及適用范圍。 HC[i]=(char * )malloc((nstart)*sizeof(char))。i++){ start=n1； for(c=i,f=HT[i].parent。 HT[s2].parent=i； //填寫雙親結(jié)點編號 HTIi].1child=s1； HT[j].rchild=s2； HT[i].weight=T[s1].weight+T[s2].weight； } // end for //從葉子到根逆向求每個字符的赫夫曼編碼 HC=(Huffmancode)malloc((n+1)*sizeof(char *))。i=n。HC /*HF編碼表 */, int *w /*各字符的權(quán)值 數(shù)組 */,){ if(n=1) return。//動態(tài)分配數(shù)組存儲 樹 Typedef char **Huffmancode。稱為赫夫曼編碼。 ?使用頻度較 高 的字符分配一個相對比較 短 的編碼， ?使用頻度較 低 的字符分配一個比較 長 的編碼。若現(xiàn)在電文為：ABACCDA，則應(yīng)發(fā)送二進制序列： 00010010101100，總長度為 14位。在設(shè)計編碼時需要遵守兩個原則： （ 1）發(fā)送方傳輸?shù)亩M制編碼，到接收方解碼后必須具有 唯一性 ，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣； （ 2）發(fā)送的二進制編碼 盡可能地短 。 ? (3) 在 F中刪除這兩棵樹 ,同時將新得到的二叉樹加入 F中 。 ? 樹的路徑長度 : 樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和 。 R A D E B C F G H K 二、后根遍歷： （ 1）依次后根遍歷每棵子樹。={T2,T3, … ,Tm} 轉(zhuǎn)換而成的二叉樹 . 第二節(jié) 森林與二叉樹的轉(zhuǎn)換 二、 二叉樹轉(zhuǎn)換成森林 ? 如果 B=(root,LB,RB)是一棵二叉樹 ,則可按如下規(guī)則轉(zhuǎn)換成森林 F={T1,T2, … ,Tm}： ? (1)若 B為空 ， 則 F為空； ? (2)若 B非空 ， 則 F中第一棵樹 T1的根 ROOT(T1)即為二叉樹 B的根 root； ? T1中的根結(jié)點的子樹森林 F1是由 B的左子樹LB轉(zhuǎn)換而成的森林 。 }CSNode, *CSTree。 int n, r。 typedef struct { TElemType data。 = 0。 //結(jié)點數(shù) }PTree。 //第 2個孩子 位置域 ...... int childd。 第一節(jié) 樹的存儲結(jié)構(gòu) R A D E F C B G K H 0 1 2 3 4 5 6 7 8 9 數(shù)組下標 : * 便于涉及孩子的操作；求雙親不方便； * 采用同構(gòu)的結(jié)點，空間浪費。 //雙親位置域 }PTNode。 //保持 pre指向 p的前驅(qū) InThreading(prchild)。plchild=pre。 //最后一個結(jié)點線索化 Thrtrchild=pre。 pre=Thrt。 ThrtRTag=Thread。 第二節(jié) 線索二叉樹 中序遍歷二叉樹 T，并將其中序線索化 : (為了記下遍歷過程中訪問結(jié)點的先后次序，附設(shè)一個全程指針 pre) Status InOrderThreading(BiThrTree amp。 //Link==0:指針 ,Thread==1:線索 typedef struct BiThrNode { TElemType data。 – 如結(jié)點 “ *” 的后繼是 “ c” 。 } return OK。 else { if (!(T=(BiTNode *) malloc(sizeof (BiTNode)))) exit(OVERFLOW)。 ? 先序序列： A B C D E F G ? 中序序列： C B E D A F G A C B E D F G A B C D E F G A B C F D E G 第一節(jié) 遍歷二叉樹 構(gòu)造二叉鏈表表示的二叉樹的遞歸算法 Status CreateBiTree(BiTree amp。 后（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹 A B C D G E F C F D B G E A 算法的遞歸描述 Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)) { if (T){ if (PostOrderTraverse(Tlchild,Visit)) if (PostOrderTraverse(Trchild,Visit)) if (Visit(Tdata)) return OK。 中（根）序的遍歷算法： 第一節(jié) 遍歷二叉樹 A B C D G E F C B D F A G E 算法的遞歸描述 Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (InOrderTraverse(Tlchild,Visit)) if (Visit(Tdata)) if (InOrderT