1、哈夫曼樹的生成及應用一、設計思想首先，我們需要建立一棵哈夫曼樹，這個過程需要使用一個數組，用來存放輸入的字符和權值，具體算法是：第一步：將所建的數組ht中的三個節點全部置為空（即左子、右子、根）。第二步：當用戶把所有的字符和權值輸入后，從這些權值中找到兩個最小的數值，把這兩個數值加和得到一個新的數值，刪除這兩個數值，并把得到的新數值放到用戶輸入的權值中。具體操作為：在當前森林ht的所有節點中，選取權值最小的和次小的根節點(least1、least2)作為合并對象，將根為htleast1和htleast2的兩棵樹最為左右子樹合并為一棵新的樹。這個過程很重要，因為只有判斷正確了，我們才能建立出一顆

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

3、的葉子節點所經過的路徑上各分支所組成的0,1序列，因此先得到的分支代碼為所求代碼的低代碼，后得到的分支代碼為所求代碼的高代碼。因此，我們可以設置兩個數組用來存放各字符的哈弗曼編碼的信息。程序中的start表示該編碼在數組code中的開始位置，所以，對于第i個字符，它的哈弗曼編碼存放在codei.start和hci.start之間的分量上。最后，需要通過先序遍歷把用戶輸入的字符輸出，具體的算法是：我們需要建立一個棧，用來存放元素，根據棧的特點，我們需要先看右子，判斷右子是否存在和是否去過，如果存在并且沒有去過，那么就將它入棧，同時把這個根節點打印出來，然后判斷左子是否存在，因為哈夫曼樹為最優二叉

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

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

6、素，根據棧的特點，我們需要先看右子，判斷右子是否存在和是否去過，如果存在并且沒有去過，那么就將它入棧，同時把這個根節點打印出來，然后判斷左子是否存在，因為哈夫曼樹為最優二叉樹，所以當右子存在時，左子一定存在，否則就是程序有問題。當判段完成后，我們需要打印左子，同時把我們規定的深度加1，把先前的左子作為根節點再次判斷。當其右子不存在是，判斷棧是否為空，不為空，則不斷地彈出一個節點，而后接著判斷，直到棧為空。第4頁3、 源代碼 下面給出的是用哈夫曼編碼和先序遍歷算法實現的程序的源代碼#ifndef Mystack_H#define Mystack_Hclass Mystack /建立一個棧供先序遍

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

8、fcode_H#define hufcode_H#include <string>using namespace std;class hufcode /建立一個用于哈弗曼編碼的類 public:string code100;int start; /最為起始節點的數據成員 ;#endif第5頁#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; /調用棧 Node ht100; /作為存放用戶輸入的數組 hufcode hc100; /作為存放哈弗曼編碼的數組 int i,j,k;int least1,least2,s1,s2;int n,m;int Parent,Lchild,Rchild;int xianxu(int i); /作為先序遍歷的成員函數 int println(int i); /打印 int SelectMin(); /挑選兩個最小值的成

10、員函數 int SetHuf(); /設置權值和數據 int bianma(); /作為哈弗曼編碼計算的成員函數;#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頁 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<<"請輸入要輸入字符的個數n="cin>>n; m=2*n-1; /總的節點數 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<<"請輸入字符：" cin>>hti.Data;cout<<"請輸入該字符的權值："cin>>hti.weight;int HufTree:SelectMin()My.initstack();this->SetHuf(); /使用同一個類中的另一個成員函數 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頁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; /找到兩個最小的分別作為左右子 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; /得到當前節點的位置 k=i; /記錄當前節點 hci.start=n; /由于是從下往上輸出，所以給個最大值 while(j!=-1) /當當前節點不是父節點時 if(htj.Lchild=k) hci.codehci.start='0' /左子為0 else if(htj.Rchild=k) hci.codehci.start='1' /右子為1 hci.start-; /向上一個 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頁cout<<endl<<"="&l

16、t;<endl;cout<<endl;cout<<"先序遍歷："<<endl;for(i=0;i<m;i+) /尋找父節點 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 權值為： "<<htParent.weight<<"t 沒有編碼"cout<<endl;htParent.kan=1; else cout<<"字符為： "<<htParent.Data<<"t 權值為： "<<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); /打印根節點 第9頁if(htParent.Lchild!=-1) xianxu(htParent.Lchild); else /如果左子不存在，從棧中取出一個值 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() /主函數 HufTree Tree;Tree.SelectMin();Tree.SetHuf();Tree.bianma()

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

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

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