数据结构课设--哈夫曼二叉树

1、数据结构课设-哈夫曼二叉树hufma ntree.h构造哈夫曼树并获得哈夫曼编码#in elude <fstream.h>#inelude <stdio.h>#in elude <stri ng.h>#in elude <proeess.h>template <elass T>struetTriNode二叉树的三叉静态链表结点Tdata;数据域intpare nt,left,righ t;父母结点和左、右孩子结点下标;classHuffma nTree哈夫曼树类private:leafNum;int叶子结点个数TriNodev int

2、>*huftree;哈夫曼树的结点数组char*hufcodes;哈夫曼编码数组public:Huffma nTree(i ntweight, int n);构造指定权值集合的哈夫曼树Huffma nTree();int deep(i nt i);void prin t(char table,char stri ng);voidprin tk(i nti,char table);/凹入输出private:void createHuffma nTree(i nt weight, i nt n);创建指定权值集合的哈夫曼树voidgetHuffma nCode();获得哈夫曼编码;void

3、Huffma nTree:pri ntk(i nt i,char table) if(i>-1)prin tk(huftreei.left,table);for(i nt j=O;jv=deep(i);j+)cout«""cout<<huftreei.data;if(i<=leafNum-1)cout<<tablei;cout«e ndl;prin tk(huftreei.right,table);/凹入表示constMax_Weight=9999;默认最大权值HuffmanTree:HuffmanTree(intwe

4、ight, int n)构造指定权值集合的哈夫曼树n个叶子结点createHuffma nTree(weight, n); getHuffma nCode();voidHuffma nTree:createHuffma nTree(i ntweight, int n)创建指定权值集合的哈夫曼树leafNum = n;huftree = new TriNode<i nt>2* n-1;/n个叶子结点的哈夫曼树共有2n-1个结点int i;for(i=0;i<n;i+)结点数组初始化有n个叶子结点huftreei.data = weighti;huftreei.pare nt=

5、huftreei.left huftreei.right = -1;for(i=0;i<n-1;i+)构造n-1个2度结点，每循环一次，构造一个 2度结点int mini, min2, x1, x2;mi n1= mi n2 = Max_Weight;选择最小和次最小权值，初值为最大权值x1=x2=-1;记录两个无父母的最小权值结点下标for (int j=0; jvn+i;j+)查找两个无父母的最小权值结点if(huftreej.data<mi n1&&huftreej.pare nt=-1)min2 = min1; x2 = x1;min1 = huftreej

6、.data;/mi n1记下最小权值x1=j;x1记下最小权值结点的下标else if (huftreej.datavmin2&&huftreej.pare nt=-1)min2 = huftreej.data;min2 记下次小权值x2 = j;x2 记下次小权值结点的下标huftreex1.pare nt=n+i;将找出的两棵权值最小的子树合并为一棵子树huftreex2.pare nt= n+i;huftree n+i.data=huftreex1.data+huftreex2.data;huftree n+i.pare nt = -1;huftree n+i .left

7、 = x1;huftree n+i.right = x2;voidHuffma nTree:getHuffma nCode()获得当前哈夫曼树的哈夫曼编码int n=leafNum;hufcodes = newchar* n;求n个叶子结点的哈夫曼编码for (int i=0; i<n; i+)char *code = newchar n;一个字符串表示一个编码code n-1='0'int start=n-1;int child = i;int pare nt = huftreechild.pare nt;while(pare nt!=-1)/由叶结点向上直到根结点循环

8、start-;if (huftreepare nteft=child)codestart='0'左孩子结点编码为0elsecodestart='1：右孩子结点编码为1child = pare nt;pare nt = huftreechild.pare nt; hufcodesi=code+start;编码数组各元素存储由start开始的字符串voidHuffma nTree:pri nt(chartable,charstri ng)ofstream fou t;fout.ope n("code.dat",ios:out); cout«&q

9、uot;n 哈夫曼编码：n"for (int i=0; i<leafNum; i+)cout<<tablei<<" : "<<hufcodesi<<endl;bool flag=false;cout«"哈夫曼编码："<<endl; for(i nt j=O;stri ngj!='O'j+)for(i=0;i<leafNum;i+)if(stri ngj=tablei) flag=true;elseflag=false;if(flag)fout<

10、;<hufcodesi; cout<<hufcodesi; fout.close();Huffma nTree:Huffma nTree() delete huftree;delete hufcodes; int Huffma nTree:deep(i nt i)in t j=0;int pare nt = huftreei.pare nt;while(pare nt!=-1)j+;parent = huftreepare nt.pare nt;return j;main .cpp#include <iostream.h>#include "Hufman

11、Tree.h" int main()int i,j,n=O;int k=O,a=O;int weight10;char string50;char table26;coutvv"输入字符串："vvendl;cin>>string;for(i=0;stringi!='0'i+)n+;for(i=0;i<n;i+)int m=0;bool flag=true;for(int p=0;p<k;p+) if(tablep=stringi) flag=false;if(flag)for(j=i;j<n;j+)if(stringi=stringj) m+;tablek=stringi;k+;coutvvkvv"号字符："<vtablek-1vv" 有"<<m<<