华北理工大学数据结构报告正文

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，右