1、哈夫曼樹的生成及應(yīng)用一、設(shè)計(jì)思想首先，我們需要建立一棵哈夫曼樹，這個(gè)過(guò)程需要使用一個(gè)數(shù)組，用來(lái)存放輸入的字符和權(quán)值，具體算法是：第一步：將所建的數(shù)組ht中的三個(gè)節(jié)點(diǎn)全部置為空（即左子、右子、根）。第二步：當(dāng)用戶把所有的字符和權(quán)值輸入后，從這些權(quán)值中找到兩個(gè)最小的數(shù)值，把這兩個(gè)數(shù)值加和得到一個(gè)新的數(shù)值，刪除這兩個(gè)數(shù)值，并把得到的新數(shù)值放到用戶輸入的權(quán)值中。具體操作為：在當(dāng)前森林ht的所有節(jié)點(diǎn)中，選取權(quán)值最小的和次小的根節(jié)點(diǎn)(least1、least2)作為合并對(duì)象，將根為htleast1和htleast2的兩棵樹最為左右子樹合并為一棵新的樹。這個(gè)過(guò)程很重要，因?yàn)橹挥信袛嗾_了，我們才能建立出一顆

2、最優(yōu)的二叉樹，否則，即使我們后面的工作做的再好，前面的哈夫曼樹沒(méi)有建正確，依舊不能達(dá)到想要的結(jié)果。第三步、重復(fù)以上過(guò)程，直到只剩下一棵樹，這顆樹就是我們要的最優(yōu)二叉樹，即哈夫曼樹。此時(shí)節(jié)點(diǎn)數(shù)與用戶輸入的字符數(shù)之間的關(guān)系是m=2*n-1；在建樹的過(guò)程中，我們默認(rèn)的規(guī)定是左子小于右子。根據(jù)網(wǎng)上的方法介紹，有兩種可以輸出哈弗曼編碼，一種是自上而下的輸出，一種是自下而上的輸出，經(jīng)過(guò)我的思考，我決定采用自下而上的尋找，同時(shí)自上而上的輸出。規(guī)定左子為0，右子為1；從葉子節(jié)點(diǎn)開始，沿節(jié)點(diǎn)的域回退到根節(jié)點(diǎn)，每回退一步，就走過(guò)了哈夫曼樹的一個(gè)分支，從而得到一位哈弗曼碼值，由于一個(gè)字符的哈弗曼碼值是從根節(jié)點(diǎn)到相應(yīng)

3、的葉子節(jié)點(diǎn)所經(jīng)過(guò)的路徑上各分支所組成的0,1序列，因此先得到的分支代碼為所求代碼的低代碼，后得到的分支代碼為所求代碼的高代碼。因此，我們可以設(shè)置兩個(gè)數(shù)組用來(lái)存放各字符的哈弗曼編碼的信息。程序中的start表示該編碼在數(shù)組code中的開始位置，所以，對(duì)于第i個(gè)字符，它的哈弗曼編碼存放在codei.start和hci.start之間的分量上。最后，需要通過(guò)先序遍歷把用戶輸入的字符輸出，具體的算法是：我們需要建立一個(gè)棧，用來(lái)存放元素，根據(jù)棧的特點(diǎn)，我們需要先看右子，判斷右子是否存在和是否去過(guò)，如果存在并且沒(méi)有去過(guò)，那么就將它入棧，同時(shí)把這個(gè)根節(jié)點(diǎn)打印出來(lái)，然后判斷左子是否存在，因?yàn)楣蚵鼧錇樽顑?yōu)二叉

4、樹，所以當(dāng)右子存在時(shí)，左子一定存在，否則就是程序有問(wèn)題。當(dāng)判段完成后，我們需要打印左子，同時(shí)把我們規(guī)定的深度加1，把先前的左子作為根節(jié)點(diǎn)再次判斷。當(dāng)其右子不存在是，判斷棧是否為空，不為空，則不斷地彈出一個(gè)節(jié)點(diǎn)，而后接著判斷，直到棧為空。至于哈弗曼的解碼，前面已經(jīng)提到當(dāng)用戶輸入字母時(shí)，就在已經(jīng)找好的編碼的編碼類中，去找到該字母。查到該字母就打印所存的哈弗曼編碼。接著就是完成用戶輸入的0、1代碼轉(zhuǎn)成字母的功能。這就需要從樹的頭結(jié)點(diǎn)向下查找，如果當(dāng)前用戶輸入的0、1中是0，則就走向左子，否則就走向右子。重復(fù)以上步驟，直到完成用戶輸入的0、1串。這樣就完成了所有的解碼的過(guò)程。第1頁(yè)2、 算法流程圖圖1

5、創(chuàng)建哈夫曼樹的流程圖建立一棵哈夫曼樹需要?jiǎng)?chuàng)造一個(gè)數(shù)組，用來(lái)存放用戶輸入的數(shù)值，首先初始化，而后判斷節(jié)點(diǎn)是否小于least1，是的話，就將它的值賦給least1，如果不是的話，就判斷是否小于least2，是的話將其賦給least2，將得到的兩個(gè)節(jié)點(diǎn)合并再次進(jìn)入循環(huán)。如果不小于least2，則結(jié)束程序。第2頁(yè)圖2 哈弗曼編碼的流程圖在進(jìn)行哈弗曼編碼過(guò)程中，我們規(guī)定左子為0，右子為1，有兩種方法可以輸出編碼，一個(gè)是自上而下的查找，一個(gè)是自下而上的查找。在查找編碼的時(shí)候需要兩個(gè)數(shù)組來(lái)確定一個(gè)節(jié)點(diǎn)的哈弗曼編碼。第3頁(yè)圖3先序遍歷輸出的流程圖在用先序遍歷輸出用戶輸入的字符時(shí)，我們需要建立一個(gè)棧，用來(lái)存放元

6、素，根據(jù)棧的特點(diǎn)，我們需要先看右子，判斷右子是否存在和是否去過(guò)，如果存在并且沒(méi)有去過(guò)，那么就將它入棧，同時(shí)把這個(gè)根節(jié)點(diǎn)打印出來(lái)，然后判斷左子是否存在，因?yàn)楣蚵鼧錇樽顑?yōu)二叉樹，所以當(dāng)右子存在時(shí)，左子一定存在，否則就是程序有問(wèn)題。當(dāng)判段完成后，我們需要打印左子，同時(shí)把我們規(guī)定的深度加1，把先前的左子作為根節(jié)點(diǎn)再次判斷。當(dāng)其右子不存在是，判斷棧是否為空，不為空，則不斷地彈出一個(gè)節(jié)點(diǎn)，而后接著判斷，直到棧為空。第4頁(yè)3、 源代碼 下面給出的是用哈夫曼編碼和先序遍歷算法實(shí)現(xiàn)的程序的源代碼#ifndef Mystack_H#define Mystack_Hclass Mystack /建立一個(gè)棧供先序遍

7、歷使用 public:int top;char cunchu;int ch100;int push(char fl);int pop();int initstack();#endif#ifndef Node_H#define Node_Hclass Node /建立一個(gè)節(jié)點(diǎn)類 public:char Data; /用于用戶輸入的字符的數(shù)據(jù)成員 int Parent; /作為根的數(shù)據(jù)成員 int Lchild; int Rchild; /作為左右子的數(shù)據(jù)成員 int weight; /作為權(quán)值的數(shù)據(jù)成員 int kan; /作為判斷該節(jié)點(diǎn)是否去個(gè)的依據(jù)的數(shù)據(jù)成員;#endif#ifndef hu

8、fcode_H#define hufcode_H#include <string>using namespace std;class hufcode /建立一個(gè)用于哈弗曼編碼的類 public:string code100;int start; /最為起始節(jié)點(diǎn)的數(shù)據(jù)成員 ;#endif第5頁(yè)#ifndef HufTree_H#define HufTree_H#include <iostream>#include <string>#include "Mystack.h"#include "hufcode.h"#inclu

9、de "Node.h"using namespace std;#define max 99999;class HufTreepublic:Mystack My; /調(diào)用棧 Node ht100; /作為存放用戶輸入的數(shù)組 hufcode hc100; /作為存放哈弗曼編碼的數(shù)組 int i,j,k;int least1,least2,s1,s2;int n,m;int Parent,Lchild,Rchild;int xianxu(int i); /作為先序遍歷的成員函數(shù) int println(int i); /打印 int SelectMin(); /挑選兩個(gè)最小值的成

10、員函數(shù) int SetHuf(); /設(shè)置權(quán)值和數(shù)據(jù) int bianma(); /作為哈弗曼編碼計(jì)算的成員函數(shù);#endif#include "Mystack.h"int Mystack:initstack() /初始化棧top=-1;int Mystack:push(char fl)top+;chtop=fl;int Mystack:pop()if(top>-1) cunchu=chtop;top-;第6頁(yè) return cunchu;#include <iostream>#include <string>#include "My

11、stack.h"#include "hufcode.h"#include "Node.h"#include "HufTree.h"using namespace std;#define max 99999;int HufTree:SetHuf() cout<<"請(qǐng)輸入要輸入字符的個(gè)數(shù)n="cin>>n; m=2*n-1; /總的節(jié)點(diǎn)數(shù) for(i=0;i<m;i+) /初始化 hti.kan=-1;hti.Parent=hti.Lchild=hti.Rchild=-1;hti

12、.Data='0'cout<<endl<<"="<<endl;for(i=0;i<n;i+) cout<<"請(qǐng)輸入字符：" cin>>hti.Data;cout<<"請(qǐng)輸入該字符的權(quán)值："cin>>hti.weight;int HufTree:SelectMin()My.initstack();this->SetHuf(); /使用同一個(gè)類中的另一個(gè)成員函數(shù) for(i=n;i<m;i+) least2=least1=

13、max;s1=s2=-1;for(j=0;j<i;j+) if(htj.Parent!=-1) continue;if(htj.weight<least1)第7頁(yè)least2=least1; least1=htj.weight;s2=s1; s1=j;else if(htj.weight<least2)least2=htj.weight;s2=j;hti.Lchild=s1;hti.Rchild=s2; /找到兩個(gè)最小的分別作為左右子 hts1.Parent=hts2.Parent=i;hti.weight=least1+least2;this->bianma();in

14、t HufTree:bianma() for(i=0;i<n;i+) j=hti.Parent; /得到當(dāng)前節(jié)點(diǎn)的位置 k=i; /記錄當(dāng)前節(jié)點(diǎn) hci.start=n; /由于是從下往上輸出，所以給個(gè)最大值 while(j!=-1) /當(dāng)當(dāng)前節(jié)點(diǎn)不是父節(jié)點(diǎn)時(shí) if(htj.Lchild=k) hci.codehci.start='0' /左子為0 else if(htj.Rchild=k) hci.codehci.start='1' /右子為1 hci.start-; /向上一個(gè) k=j; j=htj.Parent;cout<<endl<

15、;<"="<<endl;cout<<"哈夫曼樹編碼："<<endl; for(i=0;i<n;i+) cout<<" "<<hti.Data<<" 的編碼："for(j=hci.start;j<=n;j+) /從上往下輸出 cout<<" "<<hci.codej; cout<<endl;第8頁(yè)cout<<endl<<"="&l

16、t;<endl;cout<<endl;cout<<"先序遍歷："<<endl;for(i=0;i<m;i+) /尋找父節(jié)點(diǎn) if(hti.Parent=-1)Parent=i; root=i;xianxu(Parent); cout<<endl<<"="<<endl;int HufTree:println(int i) /打印 Parent=i;if(htParent.kan!=1)if(htParent.Data='0') cout<<&qu

17、ot;字符為空"<<"t 權(quán)值為： "<<htParent.weight<<"t 沒(méi)有編碼"cout<<endl;htParent.kan=1; else cout<<"字符為： "<<htParent.Data<<"t 權(quán)值為： "<<htParent.weight<<"t 編碼為： "for(j=hci.start;j<=n;j+)cout<<hcParen

18、t.codej<<" "cout<<endl;htParent.kan=1; return 0; int HufTree:xianxu(int i) /先序遍歷輸出 Parent=i; if(htParent.Rchild!=-1&&htParent.kan!=1) My.push(Parent); /右子入棧 println(Parent); /打印根節(jié)點(diǎn) 第9頁(yè)if(htParent.Lchild!=-1) xianxu(htParent.Lchild); else /如果左子不存在，從棧中取出一個(gè)值 if(My.top>-

19、1)xianxu(htMy.pop().Rchild);#include <iostream>#include <string>#include "Mystack.h"#include "hufcode.h"#include "Node.h"#include "HufTree.h"using namespace std;#define max 99999;main() /主函數(shù) HufTree Tree;Tree.SelectMin();Tree.SetHuf();Tree.bianma()

20、;system("pause");return 0;4、 運(yùn)行結(jié)果圖4是哈夫曼樹的運(yùn)行結(jié)果：首先需要用戶輸入一個(gè)n值，即用戶需要輸入的字符的個(gè)數(shù)；而后，用戶需要根據(jù)提示，先輸入一個(gè)字符，敲回車后，再輸入該字符的權(quán)值，一直如此，直到輸入最后一個(gè)字符和權(quán)值。如圖所示，用戶輸入一個(gè)n為4的值，而后敲回車，輸入第一個(gè)字符d，敲擊回車后，輸入該字符的權(quán)值7，再次敲回車后，輸入第二個(gè)字符g，依次這樣操作，直到輸入最后一個(gè)字符j和權(quán)值8，這時(shí)，用戶只需要在次敲擊一下回車，便出現(xiàn)結(jié)果中的哈弗曼編碼值。圖4哈夫曼樹的運(yùn)行結(jié)果第10頁(yè)圖5同樣是哈夫曼樹的運(yùn)行結(jié)果：同上圖一樣，當(dāng)用戶輸入最后一個(gè)

21、字符j和權(quán)值8后，敲擊回車，出現(xiàn)了上圖的哈弗曼編碼和本圖中的把用戶輸入的字符用先序遍歷的順序輸出出來(lái)。同樣如果在建立的哈夫曼樹中如果沒(méi)有該字符只是有權(quán)值，則提示字符為空和沒(méi)有編碼，但是需要把該節(jié)點(diǎn)的權(quán)值輸出。圖5哈夫曼樹的運(yùn)行結(jié)果5、 遇到的問(wèn)題及解決這部分我主要遇到了如下四個(gè)問(wèn)題，其內(nèi)容與解決方法如下所列：l 問(wèn)題1：在一開始創(chuàng)建哈夫曼樹的時(shí)候不知道如何創(chuàng)建一棵哈夫曼樹。問(wèn)題1的解決方法：后來(lái)我從網(wǎng)上找到了創(chuàng)建哈夫曼樹的方法，首先需要一個(gè)數(shù)組，用來(lái)存放用戶輸入的字符和權(quán)重。但是這是遠(yuǎn)遠(yuǎn)不夠的，我還需要知道如何建成一棵理論上的最優(yōu)二叉樹。于是我采取了如下的方法：把輸入的字符和權(quán)值分別放到ht.

22、data和ht.weight中，把每一個(gè)輸入的都作為一個(gè)根節(jié)點(diǎn)，但是其左右子都為空；從這些樹中選出兩個(gè)最小和次小的依照左子小于右子進(jìn)行合并，得到一個(gè)新的樹，這顆新的樹的左右子為剛才的兩個(gè)樹，這時(shí)刪除先前的兩顆樹，并將得到的新樹放到原來(lái)的森林中，如此循環(huán)，知道森林中只有一棵樹。這樣一棵哈夫曼樹就建好了。同時(shí)在建造樹的過(guò)程中，我也遇到了邏輯上的問(wèn)題，比如循環(huán)時(shí)候的范圍，在經(jīng)過(guò)和舍友的討論后，最終將程序運(yùn)行了出來(lái)。l 問(wèn)題2：對(duì)于如何實(shí)現(xiàn)哈弗曼編碼的輸出和尋找。問(wèn)題2的解決方法：根據(jù)網(wǎng)上的方法介紹，有兩種可以輸出哈弗曼編碼，一種是自上而下的輸出，一種是自下而上的輸出，經(jīng)過(guò)我的思考，我決定采用自下而上的尋找，同時(shí)自上而上的輸出。規(guī)定左子為0，右