哈夫曼树介绍
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+ Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
哈夫曼树的建立
由哈夫曼最早给出的建立最优二叉树的带有一般规律的算法，俗称哈夫曼算法。描述如下：
- 初始化：根据给定的n个权值(Ｗ1,Ｗ2,…，Ｗn)，构造n棵二叉树的森林集合F={Ｔ1,Ｔ2,…,Ｔn}，其中每棵二叉树Ｔi只有一个权值为Ｗi的根节点，左右子树均为空。
- 找最小树并构造新树：在森林集合F中选取两棵根的权值最小的树做为左右子树构造一棵新的二叉树，新的二叉树的根结点为新增加的结点，其权值为左右子树的权值之和。
- 删除与插入：在森林集合F中删除已选取的两棵根的权值最小的树，同时将新构造的二叉树加入到森林集合F中。
- 重复2)和3)步骤，直至森林集合F中只含一棵树为止，这颗树便是哈夫曼树，即最优二叉树。由于2)和3)步骤每重复一次，删除掉两棵树，增加一棵树，所以2)和3)步骤重复n-1次即可获得哈夫曼树
设终端节点数为n0，度为二的节点数为n2，度为一的节点数为n1，总结结点个数为n，分支数目为B
1.n=n0+n1+n2
2.n=B+1
3.B=n1+2*n2；
4.n0=n2+1;
哈夫曼编码
在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
哈夫曼译码
在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。
问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统
代码实现：
#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std; typedef struct HTNode
{
int weight;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree; //封装最小的权和次小的全
typedef struct
{
int p1,p2;
}*MinCode; static char N[];
typedef char **HuffmanCode;//Huffman编码 //当输入1个结点时，提示输出错误
void Error(const char *message)
{
cerr<<"Errors: "<<message<<endl;
exit();//非return,如果return 会造成main函数HT[i]无值
} //
MinCode Select(HuffmanTree HT,int n)
{
int Min=0x3f3f,p1=,p2=;
//找出权值weight最小的结点，下标保存在p1中
for(int i=;i<=n;++i)
if(HT[i].weight<Min&&HT[i].parent==)
{
Min=HT[i].weight;
p1=i;
}
//找出权值weight次小的结点，下标保存在p1中
int SecMin=0x3f3f;
for(int i=;i<=n;++i)
if((HT[i].weight<SecMin)&&(i!=p1)&&(HT[i].parent==))
{
SecMin=HT[i].weight;
p2=i;
} //封装进结构体中
MinCode Code;
Code->p1=p1;
Code->p2=p2; return Code;
} //构造HUffman树HT，编码存放在HC中，w为权值，n为结点个数
HuffmanCode huffman_codeing(HuffmanTree &HT,HuffmanCode HC,int *w,int n)
{
if(n<=)
Error("Code to samll."); int m=*n-;
HT=new HTNode[m+];//第0个空间不用，故申请m+1个空间 //初始化n个叶子结点
HuffmanTree p=HT;
int i=;
for(++p,++w;i<=n;++i,++p,++w)
{
p->weight=*w;
p->lchild=p->rchild=p->parent=;
}
//n-1个非叶子结点初始化
for(;i<=m;++i,++p)
p->weight=p->parent=p->lchild=p->rchild=; //构造Huffman树
MinCode Min;
int p1=,p2=;
for(i=n+;i<=m;++i)
{
Min=Select(HT,i-);//找出最小和次小连个结点
p1=Min->p1;//最小下标
p2=Min->p2;//次小下标
HT[p1].parent=i;
HT[p2].parent=i;//最小下标和次小下标同一树，双亲相同
HT[i].lchild=p1;//i结点的左孩子
HT[i].rchild=p2;//i结点的右孩子
HT[i].weight=HT[p1].weight+HT[p2].weight;//i结点的权值
} //打印Huffman树
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(int i=;i<=m;i++)
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); //从叶子结点到根结点求每个字符的Huffman编码
HC=new char*[n+];
//为Huffman编码动态分配空间
char *cd=new char[n];
cd[n-]='\0';//3个结点的Huffman编码最长为2 //求叶子结点的Huffman编码
for(int i=;i<=n;++i)
{
int start=n-;
//左子树为0右子树为1，从最下边1号开始往上编码(逆序存放)，然后2号结点，3号...
for(int c=i,f=HT[i].parent;f>;c=f,f=HT[f].parent)
if(HT[f].lchild==c)
cd[--start]='';
else
cd[--start]=''; //为第i个字符分配空间
HC[i]=new char[n-start];
//将Huffman编码复制到HC
strcpy(HC[i],&cd[start]);
}
free(cd);
return HC;
} //译码
void huffman_translate_codeing(HuffmanTree HT,int n,char *ch)
{
int m=*n-,i,j=;
cout<<"After Translation:"<<endl; while(ch[j]!='\0')//要译码的串
{
i=m;
while(HT[i].lchild!=&&HT[i].rchild!=)//从顶部向下找
{
if(ch[j]=='')//0往左走
i=HT[i].lchild;
else//1往右走
i=HT[i].rchild; ++j;
}
cout<<N[i-];
}
cout<<endl;
} int main()
{
cout<<"Input N(char):";
cin.getline(N,,'\n');
cin.clear();//清空输入流
cin.sync(); int len=strlen(N);
int *w=new int[len+]; cout<<"Enter weight:"<<endl;
for(int i=;i<=len;++i)
{
cout<<"w["<<i<<"]=";
cin>>w[i];
}
cin.clear();//清空输入流
cin.sync(); HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
HC=huffman_codeing(HT,HC,w,len); //输出Huffman编码
cout<<"HuffmanCode:" <<endl;
printf("Number\t\tWeight\t\tCode\n");
for(int i=;i<=len;i++)
{
printf("%c\t\t%d\t\t%s\n",N[i-],w[i],HC[i]);
}
cin.clear();//清空输入流
cin.sync(); //译码
char tran[];
cout<<"Input HuffmanTranslateCodeing(like 101010):";
cin.getline(tran,,'\n');
huffman_translate_codeing(HT,len,tran); free(HT);
free(HC);
return ;
}