哈夫曼树的建立及应用

哈夫曼树的建立及应用1、给定权值5，29，7，8，14，23，3，11，建立哈夫曼树，输出哈夫曼编码。2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二进制编码，输出它的哈夫曼译码。三、算法描述将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数中调用它们。建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。程序清单：#includeiostream#includeiomanipusingnamespacestd;constintn=8;constintm=2*n-1;structTree//哈夫曼树的一个结点{intparent,lchild,rchild;//双亲，左孩子，右孩子intweight;//权值};structcodetype//哈夫曼编码{intbits[n+1];//编码存放的位置intstart;//编码开始存放的位置charch;//编码对应的字符};TreehuffTree[m+1];codetypecode[n+1];voidSelect()//搜索权值最小的两个数并合并成哈夫曼树{intx,y;intj,min1,min2;for(intk=n+1;k=m;k++)//合并成哈夫曼树{min1=min2=32767;x=y=0;for(j=1;j=k-1;j++)//找出权值最小的两个数if(huffTree[j].parent==0)if(huffTree[j].weightmin1){min2=min1;min1=huffTree[j].weight;y=x;x=j;}elseif(huffTree[j].weightmin2){min2=huffTree[j].weight;y=j;}huffTree[x].parent=k;huffTree[y].parent=k;huffTree[k].lchild=x;huffTree[k].rchild=y;huffTree[k].weight=huffTree[x].weight+huffTree[y].weight;}}voidHuffmanTree()//构造哈夫曼树{for(inti=1;i=m;i++){huffTree[i].parent=0;huffTree[i].lchild=0;huffTree[i].rchild=0;huffTree[i].weight=0;}cout请输入n个权值endl;for(i=1;i=n;i++)cinhuffTree[i].weight;Select();}voidHuffcode()//哈夫曼编码{codetypecd;intc,p;for(inti=1;i=n;i++){cd.start=n+1;cd.ch=96+i;//第一个字符为a，并依次排字符c=i;p=huffTree[i].parent;while(p!=0){cd.start--;if(huffTree[p].lchild==c)cd.bits[cd.start]=0;elsecd.bits[cd.start]=1;c=p;p=huffTree[p].parent;}code[i]=cd;}for(i=1;i=n;i++){cout字符code[i].ch的权值为：huffTree[i].weightsetw(5)编码是：;for(intj=code[i].start;j=n;j++)coutcode[i].bits[j];coutendl;}}voidtranHuffcode()//哈夫曼译码{inti=m;charb;cout请输入一串二进制编码以（0和1以外的数结束）endl;cinb;while((b=='0')||(b=='1')){if(b=='0')i=huffTree[i].lchild;elsei=huffTree[i].rchild;if(huffTree[i].lchild==0){coutcode[i].chendl;//译码成功，输出字符i=m;}cinb;}}voidmain(){HuffmanTree();//建立哈夫曼树Huffcode();//实现哈夫曼编码tranHuffcode();//实现哈夫曼译码}运行结果：