哈夫曼树的建立及应用

哈夫曼树的建立及应用

1、 给定权值5，29，7，8，14，23，3，11，建立哈夫 曼树，输出哈夫曼编码。

2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二 进制编码，输出它的哈夫曼译码。

三、算法描述

将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数中调用它们。

建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。

要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。

程序清单：

#include #include using namespace std; constint n=8;

constint m=2*n-1;

struct Tree //哈夫曼树的一个结点 {

intparent,lchild,rchild; //双亲，左孩子，右孩子 int weight; //权值 };

structcodetype //哈夫曼编码 {

int bits[n+1]; //编码存放的位置 int start; //编码开始存放的位置 char ch; //编码对应的字符 };

Tree huffTree[m+1]; codetype code[n+1];

void Select() //搜索权值最小的两个数并合并成哈夫曼树 {

intx,y;

int j,min1,min2;

for(int k=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].weight

min2=min1;

min1=huffTree[j].weight ; y=x; x=j; }

else if(huffTree[j].weight

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; } }

void HuffmanTree() //构造哈夫曼树 {

for(inti=1;i<=m;i++) {

huffTree[i].parent=0; huffTree[i].lchild=0; huffTree[i].rchild=0; huffTree[i].weight=0; }

cout<<\请输入\个权值\ for(i=1;i<=n;i++)

cin>>huffTree[i].weight;

Select(); }

void Huffcode() //哈夫曼编码 {

codetype cd; 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; else

cd.bits[cd.start]=1; c=p;

p=huffTree[p].parent; }

code[i]=cd; }

for(i=1;i<=n;i++) {

cout<<\字符\的权值为\编码是：\ for(int j=code[i].start;j<=n;j++) cout<

void tranHuffcode() //哈夫曼译码 {

inti=m;char b;

cout<<\请输入一串二进制编码以（0和1以外的数结束）\ cin>>b;

while((b=='0')||(b=='1')) {

if(b=='0')

i=huffTree[i].lchild;

：

else

i=huffTree[i].rchild; if(huffTree[i].lchild==0) {

cout<

cin>>b; } }

void main() {

HuffmanTree(); //建立哈夫曼树 Huffcode(); //实现哈夫曼编码

tranHuffcode(); //实现哈夫曼译码 }

运行结果：

本文来源：https://www.bwwdw.com/article/nht5.html