【正文】 本章小結 作 業(yè) 書面作業(yè) : p38: ， p39: p40: p41: p43: 上機作業(yè) : (使用棧非遞歸實現，三種遍歷任選一種，前序中序滿分 4分，后序滿分 5分 ) 2. 哈夫曼編 /譯碼器 (p149) 。 ?理解最優(yōu)樹的特性，掌握建立最優(yōu)樹和 Huffman編 碼的方法 。cd[start])； //從 cd復制編碼 (串 )到 Hc } free(cd)； //釋放工作空間 } //HuffanCoding 定義和性質 存儲結構 遍歷 線索化：線索樹 順序結構 鏈式結構 二叉鏈表 三叉鏈表 先序線索樹 中序線索樹 后序線索樹 樹 二叉樹 森林 先 序 遍 歷 中 序 遍 歷 遍歷 存儲結構 遍歷 雙親表示 孩子表示 孩子兄弟 先序遍歷 后序遍歷 中序遍歷 后序遍歷 先序遍歷 Huffman樹 定義 ,構造 ,編碼 本章小結 ?理解樹形結構的基本概念和術語； ?深刻領會 二叉樹的定義和存儲結構，熟悉二叉樹的 遍歷并熟練掌握遍歷算法 ； ?理解二叉樹線索化的實質，熟練掌握二叉樹的線索 化過程以及遍歷中序線索二叉樹的方法 。 for(i=1。 //分配 n個字符編碼的頭指針向量 cd=(char*)malloc(n*sizeof(char))； //分配求編碼的工作空間 cd[n1]=＼ 0。 HT[i].lchild=s1。 i=m； ++i， ++p) *p={0， 0， 0， 0}； //后 n1個結點 for(i=n+1； i=m； ++i){ //建哈夫曼樹 //在 HT[1..i1]選擇 parent為 0且 weight最小的兩個結點，其序號分別為 s1和 s2。 i=n。 if(n=1) return； m=2*n1。HT， HuffmanCode amp。 問題 : 如何證明所構造的二叉樹是最優(yōu)樹 ? 例 : 已知權值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 6 7 3 8 5 9 例 : 已知權值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 3 8 5 7 6 13 9 例 : 已知權值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 7 6 13 3 8 5 9 17 例 : 已知權值 W={ 5, 6, 3, 9, 7 } 5 6 3 7 9 3 8 5 9 17 7 6 13 30 用 n個葉結點構造出的最優(yōu)二叉樹共有幾個結點？ ?構造最優(yōu)樹時共執(zhí)行 n1次循環(huán)，每次增加一個新 結點，共增加了 n1個結點，所以結點總數一定 是 n+n1=2n1 ?因為 n0=n2+1, 所以 n2=n01, 又由于在 最優(yōu)二叉樹中 沒有度為 1的結點 ,所以在最優(yōu)二叉樹中總的結點數為 n+n1=2n1 Huffman 算法的實現： Huffman編碼： 設字符集為 {c1 , c2 ,…, c n} , 看作葉結點 出現概率為 {w1 , w2 ,…, w n} ,葉結點的權 （ 1）構造 Huffman樹 （ 2）左分支標 0，右分支標 1 （ 3）根到葉結點 ci的路徑上的二進制編碼就是 ci的編碼 編碼長度為 { l1 , l2 ,…, l n} 是葉結點的路徑長度 , 則 樹的帶權路徑長度 WPL是： ???nkkk lwW P L1 根 到任何 ci的路徑都不會經過任何其它 ck, 因此 Huffman編碼是 無前綴編碼 ，即任何一個編碼都不 會是另一個編碼的前綴。 3. 從 F中刪除 Ti和 Tj ， 加入新的樹 R到 F中。 二、構造 huffman樹 算法思想： 1. 根據權值 {w1 , w2 ,…, w n}構造 n個二叉樹 F={T1 , T2 , …, T n}， 其中 Ti中是只含權值為 wi 的結點。 一、哈夫曼樹 (最優(yōu)樹 )的定義 ??nkkklw1例 W={1,2,4,6} ,可構造出如下的二叉樹： 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) 根據定義求 Huffman樹的方法是： 對給定的 n個葉子結點（外部結點），構造出全部二叉樹并求出其 WPL， 然后找出 WPL最小的樹。 樹的路徑長度 ：樹中每個結點的路徑長度之和。 任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。 1). 森林 =二叉樹的轉換 自然轉換法： 凡是 兄弟 用線連起來，然后去掉雙親到子女的連線， 但保留雙親到其第一子女的連線，最后轉 45176。 ?先序遍歷第一棵樹中的根 結點的子樹森林； ?先序遍歷其余的樹所構成 的森林； A B C D E F G H I J 中序遍歷序列： BCDAFEHJIG 中序遍歷森林 二、 樹與森林的遍歷 中序遍歷 : ?中序遍歷第一棵樹的子樹； ?訪問第一棵樹的根 。 ? 先序遍歷第一棵樹中的根結點的子樹森林； ? 先序遍歷其余的樹所構成的森林； (2) 中序遍歷 : ? 中序遍歷第一棵樹的子樹； ? 訪問第一棵樹的根 。 ? 訪問根結點 。 ? 從左到右先根遍歷根的每棵子樹 。 ChildPtr firstchild。表頭數組中每一項稱孩子鏈表頭指針 CTBox: (頭結點 ) 單鏈表中每一項稱孩子結點 (也稱表結點 )： CTNode: 一、 樹的存儲結構 data firstchild child next typedef struct CTNode { //孩子結點（ 表結點） int child； struct CTNode *next； } *ChildPtr； tyPedef struct { //頭結點 TElemType data； ChildPtr firstchild。 這種方法不可取 。 //樹的結點數 } PTree。 typedef struct { PTNode nodes[MAXTREESIZE]。 int parent。 } } } // PreOrderTraverse 雙親表示法 是一種順序存儲方法，即用數組存儲。 if (r) p=rrchild。amp。 // P有右子女 else{ r=prchild。 if (!pltag) p=plchild。 前序遍歷線索二叉樹的算法 void PreOrderTraverse(BiThrTree BT){ p=BT。 } } // inOrderTraverse 中序遍歷線索二叉樹的算法 同理，我們可以前序非遞歸遍歷中序線索二叉樹， 同樣不需要遞歸（使用了系統(tǒng)棧）也不需要棧 . 關鍵問題 1 根就是第一個結點 . 關鍵問題 2，有如下 3種情況： ?P有左子女：則 p左子女是 p的后繼；否則 ?P有右子女：則 p的右子女是 p的后繼 。 visit(p)。amp。 //沿左鏈走直到無左子女的結點 visit(p)。 } 中序遍歷 (中序 )線索二叉樹時如何解決這兩個問題 : void InOrderTraverse(BiThrTree BT) { p=BT。 // P無右子女 else { p=prchild。 關鍵問題 2，有如下兩種情況： ?P無右子女：則 prchild是 p的后繼； ?P有右子女：則 p的右子樹中最左的結點就是 p的后繼，方法同 關鍵問題 1。 p=BT。 2) 找出給定結點 p在某一次序中的后繼結點 。 p=prchild。 =true。amp。 =true。 } // p指向左子女 else { pop(S,p)。 //p指向根 ,pre是 p的前驅結點 while (p || !StackEmpty(S)) { if (p) { push(S,p)。 //建立棧 p=BT。 lchild Ltag data Rtag rchild 二、線索二叉樹 (Threaded Binary Tree) 加了線索的二叉樹是 線索二叉樹 ； 給二叉樹加線索的過程是 線索化（穿線） ； 按前序遍歷序列穿線的二叉樹是 前序線索二叉樹 ； 按中序遍歷序列穿線的二叉樹是 中序線索二叉樹 ； 按后序遍歷序列穿線的二叉樹是 后序線索二叉樹 ； 中序線索 二叉樹簡稱 線索二叉樹 ； 二、線索二叉樹 (Threaded Binary Tree) A B C D E A B D C E T 先序序列： ABCDE 先序線索二叉樹 0 0 0 0 1 1 1 1 ^ 1 1 二、 線索二叉樹 (Threaded Binary Tree) A B C D E A B D C E T 中序序列： BCAED 中序線索二叉樹 0 0 0 0 1 1 1 1 ^ 1 1 ^ 二、 線索二叉樹 (Threaded Binary Tree) A B C D E A B D C E T 后序序列： CBEDA 后序線索二叉樹 0 0 0 0 1 1 1 1 1 1 ^ 二、 線索二叉樹 (Threaded Binary Tree) D B F E A C NULL NULL 中序線索二叉樹 二、線索二叉樹 (Threaded Binary Tree) Void lnorderTraverse(BiTree BT) { ／／ 采用二叉鏈表存儲結構，中序遍歷二叉樹 T的非遞歸算法 . InitStack(S)； p=BT； while(p||!StackEmpty(S)) { if(p) { push(S， p)； p=plchild； }//根指針進棧，遍歷左子樹 else { ／／ 根指針退棧，訪問根結點，遍歷右子樹 pop(S， p)； visit(p)。 PointerTag Ltag, Rtag。 Typedef struct BiThrNode { ElemType data。 ? 用空的 左指針 指向某一遍歷序列的 前驅 . ? 用空的 右指針 指向某一遍歷序列的 后繼 . 這 兩種指針 稱為 線索 (Thread)。 } // p指向右子女 } // else } // end of while } // end of postOrderTraverse (bt) 例 B E A C Start (A,L) 入棧 (A,L) (B,L) 入棧