【正文】 (a) 權(quán)值之和為 5 (b) 其權(quán)值之和為 10 (c) 其權(quán)值之和為 19 圖 627 哈夫曼樹建立過程 帶權(quán)路徑長度為： WPL=9*1+5*2+3*3+2*3=34 對于同一組給定葉結(jié)點權(quán)值所構(gòu)造的哈夫曼樹 ， 樹的形狀可能不同 ， 但其帶權(quán)路徑長度值是相同的 ， 而且必定是最小的 。 2 3 5 10 5 5 2 3 19 9 10 5 5 2 3 【 例 612】 設(shè)結(jié)點的權(quán)集 W ={10， 12， 4， 7， 5， 18， 2}，建立一棵哈夫曼樹 ， 并求出其帶權(quán)路徑長度 。 圖 628 哈夫曼樹建立過程 2． 哈夫曼樹的構(gòu)造算法 （ 了解 ） 663 哈夫曼編碼 1． 什么是哈夫編碼 ？ 在數(shù)據(jù)通訊中 ， 經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符 0， 1組成的二進制代碼 ， 稱之為編碼 。 如果在編碼時考慮字符出現(xiàn)的頻率 ， 讓出現(xiàn)頻率高的字符采用盡可能短的編碼 ， 出現(xiàn)頻率低的字符采用稍長的編碼 ，構(gòu)造一種不等長編碼 ， 則電文的代碼就可能更短 。 哈夫曼編碼是一種用于構(gòu)造使電文的編碼總長最短的編碼方案 。 2． 求哈夫曼編碼的方法 （ 1） 構(gòu)造哈夫曼樹 設(shè)需要編碼的字符集合為 {d1， d2， … ， dn}， 它們在電文中出現(xiàn)的次數(shù)集合為 {w1， w2， … ， wn}， 以 d1， d2， … ，dn作為葉結(jié)點 ， w1， w2， … ， wn作為它們的權(quán)值 ， 構(gòu)造一棵哈夫曼樹 。 【 例 613】 設(shè)有 A， B， C， D， E， F 6個數(shù)據(jù)項 ， 其出現(xiàn)的頻度分別為 1， 構(gòu)造一棵哈夫曼樹 ， 并確定它們的哈夫曼編碼 。 構(gòu)造一棵哈夫曼樹 ， 并確定它們的哈夫曼編碼 。 圖 629 構(gòu)造哈夫曼樹到哈夫曼編碼的過程 （ 2） 在哈夫曼樹上求葉結(jié)點的編碼 。 規(guī)定哈夫曼樹中的左分支代表 0， 右分支代表 1， 則從根結(jié)點到每個葉結(jié)點所經(jīng)過的路徑分支組成的 0和 1的序列便為該結(jié)點對應(yīng)字符的編碼 ， 如圖 629（ b） 編碼為： A=11； B=01； C=00； D=100； E=1011； F=1010。 在哈夫曼編碼樹中 ， 樹的帶權(quán)路徑長度的含義是各個字符的碼長與其出現(xiàn)次數(shù)的乘積之和 ， 也就是電文的代碼總長 。 采用哈夫曼樹構(gòu)造的編碼是一種能使電文代碼總長為最短的 、 不等長編碼 。 求哈夫曼編碼 ， 實質(zhì)上就是在已建立的哈夫曼樹中 ， 從葉結(jié)點開始 ， 沿結(jié)點的雙親鏈域回退到根結(jié)點 ， 每回退一步 ， 就走過了哈夫曼樹的一個分支 ， 從而得到一位哈夫曼碼值 ， 由于一個字符的哈夫曼編碼是從根結(jié)點到相應(yīng)葉結(jié)點所經(jīng)過的路徑上各分支所組成的 0， 1序列 ， 因此先得到的分支代碼為所求編碼的低位碼 ， 后得到的分支代碼為所求編碼的高位碼 。 *3． 哈夫曼樹及哈夫曼編碼的程序： include define MAXLEN 100 typedef struct // 定義結(jié)構(gòu)體 {int weight。 // 定義一個整型權(quán)值變量 int lchild,rchild,parent。 // 定義左 、 右孩子及雙親指針 }HTNode。 typedef HTNode HFMT [MAXLEN]。 // 是向量類型的 int n。 void InitHFMT (HFMT T) // 初始化 {int i。 printf (\n\t\t請輸入共有多少個權(quán)值 (小于 100)： )。 scanf (%d,amp。n)。getchar()。 for (i=0。 i2*n1。 i++) {T[i].weight=0。 T[i].lchild=1。 T[i].rchild=1。 T[i].parent=1。 } } 小 結(jié) void InputWeight(HFMT T) // 輸入權(quán)值 {int w。 int i。 for (i=0。 in。i++) {printf (\n\t\t輸入第 %d個權(quán)值 :,i+1)。 scanf (%d,amp。w)。getchar()。 T[i].weight=w。 } } void SelectMin (HFMT T, int i, int *p1,int *p2) // 選擇兩個結(jié)點中小的結(jié)點 {long min1=999999。 // 預(yù)設(shè)兩個值 ， 并使它大于可能出現(xiàn)的最大權(quán)值 long min2=999999。 int j。 for (j=0。j=i。j++) {if (T[j].parent==1) {if (min1T[j].weight) {min1=T[j].weight。 // 找出最小的權(quán)值 *p1=j。 // 通過 *p1帶回序號 } } } for (j=0。j=i。j++) {if (T[j].parent==1) {if (min2T[j].weightamp。amp。j!=(*p1)) {min2=T[j].weight。 // 找出次最小的權(quán)值 *p2=j。 // 通過 *p2帶回序號 } } } } // 選擇結(jié)束 void CreatHFMT (HFMT T) // 構(gòu)造哈夫曼樹 ， T[2*n1]為其根結(jié)點 {int i,p1,p2。 InitHFMT (T)。 InputWeight (T)。 for (i=n。i2*n1。i++) { SelectMin (T,i1,amp。p1,amp。p2)。 T[p1].parent=T[p2].parent=i。 T[i].lchild=T[p1].weight。 T[i].rchild=T[p2].weight。 T[i].weight=T[p1].weight+T[p2].weight。 } } void PrintHFMT (HFMT T) // 輸出向量狀態(tài)表 {int i,k=0。 for (i=0。 i2*n1。 i++) while (T[i].lchild!= 1) { if (!(k%2)) printf (\n)。 printf(\t\t(%d%d),(%d%d),T[i].weight, T[i].lchild,T[i].weight,T[i].rchild)。 k++。break。 } } void hfnode (HFMT T,int i,int j) {j=T[i].parent。 if (T[j].rchild= =T[i].weight) printf(1)。 else printf(0)。 if(T[j].parent!= 1) i=j,hfnode (T,i,j)。 } void huffmannode (HFMT T) // 求哈夫曼編碼 { int i,j,a,k=0。 printf (\n)。 for (i=0。in。i++) { j=0。 a=i。 if (!(k%2)) printf (\n)。 printf(\t\t%i: ,T[i].weight)。k++。 hfnode(T,i,j)。 i=a。 } } void main() // 主函數(shù) { HFMT HT。 CreatHFMT(HT)。 PrintHFMT(HT)。 huffmannode(HT)。 printf(\n)。 } （ 1） 樹是一種以分支關(guān)系定義的層次結(jié)構(gòu) ， 除根結(jié)點無直接前趨 ， 其余每個結(jié)點有且僅有一個直接前趨 ， 但樹中所有結(jié)點都可以有多個直接后繼 。 樹是一種具有一對多關(guān)系的非線性數(shù)據(jù)結(jié)構(gòu) 。 （ 2） 一棵非空的二叉樹 ， 每個結(jié)點至多只有兩棵子樹 ，分別稱為左子樹和右子樹 ， 且左右子樹的次序不能任意交換 。 它的左 、 右子樹又分別都是二叉樹 。 二叉樹是本章的重點 ， 必須重點掌握 。 （ 3） 若所有分支結(jié)點都存在左子樹和右子樹 ， 且所有葉子結(jié)點都在同一層上 ， 這樣的一棵二叉樹就是滿二叉樹 。若除最后一層外 ， 若其余各層都是滿的 ， 并且最后一層或者為滿 ， 或者僅在右邊缺少連續(xù)若干個結(jié)點 ， 則稱此二叉樹為完全二叉樹 。 要求熟悉二叉樹 、 滿二叉樹和完全二叉樹之間的一些基本性質(zhì) 。 小 結(jié) （ 4） 二叉樹的遍歷是指按某種順序訪問二叉樹中的所有結(jié)點 ， 使得每個結(jié)點都被訪問 ， 且僅被訪問一次 。 通過一次遍歷 ， 使二叉樹中結(jié)點的非線性排列轉(zhuǎn)變線性排列 。 要求熟練掌握二叉樹的前根遍歷 、 中根遍歷 、 后根遍歷和層次遍歷的概念和算法 。 （ 5） 二叉樹具有順序存儲和鏈?zhǔn)酱鎯煞N存儲結(jié)構(gòu) 。 在順序存儲時 ， 若采用一維數(shù)組則必須按完全二叉樹格式存儲；在二叉鏈?zhǔn)酱鎯r ， 每個結(jié)點有兩個指針域 ， 具有 n個結(jié)點的二叉樹共有 2n個指針 ， 其中指向左 、 右孩子的指針有 n1個 ， 空指針有 n+1個 。 （ 6） 利用二叉樹 n+1個空指針來指示某種遍歷次序下的直接前趨和直接結(jié)后繼 ， 這就是二叉樹的線索化 。 （ 7） 一般樹的存儲比較麻煩 ， 但只要將一般樹轉(zhuǎn)換為二叉樹存儲就比較方便了 。 要求掌握一般樹轉(zhuǎn)換為二叉樹的方法 。 （ 8） 用二叉樹表示圖形數(shù)據(jù)結(jié)構(gòu)時 ， 如果去掉結(jié)點的指針項 ， 只按結(jié)點的中序序列存儲 ， 并給出這棵樹的前序（ 或后序 ） “ 序表 ” ；圖形調(diào)入內(nèi)存時 ， 由中序的結(jié)點表及前序 （ 或后序 ） “ 序表 ” 來恢復(fù)二叉樹 ， 是數(shù)據(jù)結(jié)構(gòu)中的一種重要應(yīng)用 。 （ 9） 將算術(shù)表達式用二叉樹來表示稱為標(biāo)識符樹 ， 也稱為二叉表示樹 ， 利用表識符樹的后序遍歷可以得到算術(shù)表達式的后綴表達式 ， 是二叉樹的一種應(yīng)用 。 （ 10） 帶權(quán)路徑長度最小的二叉樹稱為哈夫曼樹 ， 要求能按給出的結(jié)點權(quán)值的集合 ， 構(gòu)造哈夫曼樹 ， 并求帶權(quán)路徑長度 。 在程序設(shè)計中 ， 對于多分支的判別 （ 各分支出現(xiàn)的頻度不同 ） ， 利用哈夫曼樹可以提高程序執(zhí)行的效率 ， 必須予以重點掌握 。 哈夫曼編碼在通信中有著廣泛的應(yīng)用 ，應(yīng)該有一定的了解 。 1． 實驗?zāi)康? （ 1） 掌握二叉樹的特點及其存儲的方式 。 （ 2） 掌握二叉樹的創(chuàng)建和顯示方法 。 （ 3） 復(fù)習(xí)二叉樹遍歷的概念 ， 掌握二叉樹遍歷的基本方法 （ 4） 掌握求二叉樹的葉結(jié)點數(shù) 、 總結(jié)點數(shù)和深度等基本算法 。 2． 實驗內(nèi)容 （ 1） 按屏幕提示用前序方法建立一棵二叉樹 ， 并能按凹入法顯示二叉樹結(jié)構(gòu)； （ 2） 編寫前序遍歷 、 中序遍歷 、 后序遍歷 、 層次遍歷程序 。 （ 3） 編寫求二叉樹的葉結(jié)點數(shù) 、 總結(jié)點數(shù)和深度的程序 。 （ 4） 設(shè)計一個選擇式菜單 ， 以菜單方式選擇下列操作 。 實驗 6 樹子系統(tǒng) 二 叉 樹 子 系 統(tǒng) ******************************************** * 1建 二 叉 樹 * * 2凹 入 顯 示 * * 3先 序 遍 歷 * * 4中 序 遍 歷 * * 5后 序 遍 歷 * * 6層 次 遍 歷 * * 7求 葉 子 數(shù) * * 8求 結(jié) 點 數(shù) * * 9求 樹 深 度 *