哈夫曼树（结合王卓老师课程内容）
目录
1、哈夫曼树的基本概念
| 路径 | 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 |
| 路径长度 | 路径上的分支数目称作路径长度。 |
| 树的路径长度 | 从树根到每一结点的路径长度之和。 |
| 结点的带权路径长度 | 从该结点到树根之间俺的路径长度与结点上权值的乘积。 |
| 树的带权路径长度 | 树中所有叶子结点的带权路径长度之和。（WPL） |
2、哈夫曼树的构造方法
██ 哈夫曼算法口诀：1、构造森林全是根；2、选用两小造新树；3、删除两小添新人；4、重复2、3剩单根。
██ 上面的例子，有四个结点，由哈夫曼算法口诀，先找出两个小的结点，即 c 和 d，由 c 和 d结合造一棵新树 ，即图中蓝色区域，然之后在第一个黑框中重复2、3；即在7，5，6这三个结点里选择另个小的结点，组成一棵树即绿框区域。接着再将7,11，这两个结点结合成一棵树。
✔总结哈夫曼树的特点：
1、哈夫曼树的结点的度数为0或者2，没有度为1的结点。
2、在哈夫曼算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树。
3、经过n-1次合并产生n-1个新结点，且n-1个新结点都是具有两个孩子的分支结点。
所以哈夫曼树中共有2n-1个结点，且其所有的分支结点的度均不为1.
3、哈夫曼树的算法实现
先分析：
第一步：
采用顺序储存结构——一维结构数组
（哈夫曼树中共有2n-1个结点，我们不适用0下标，所以定义数组大小为2n）
举个栗子：
有n=8,权值为W={7，19，2，6，32，3，21，10} 构造哈夫曼树。
由上面的哈夫曼算法口诀“构造森林全是根”，所以先将结点的父母和左右子树全置为0.然后将结点1-8的权值先附上。
第二步：
然后口诀里的下一步是“选用两小造新树”，那么我们就在1-8里找权值最小的，也就是2和3，然后我们就把它们结成一个新树，如上右图。第三句口诀是“删除两小添新人”。删除也就是把两个权值小的结点的双亲改为非0. 添新人，也就是把合并两个小的权值作为一个新结点的权值依次存放如数组。在这里例子里，也就是2和3的权值和为5，那就将5存放在9的位置。（完成添新人这一操作） 然后将权值为2和3的结点的双亲改为9. （完成删两小这一操作） 那么这一步的操作就完成了。接下来依次循环。那么最后的哈夫曼树如下：
再实现：
第一步 ：
也就是口诀里的第一步“构造森林全是根”。 上面例子的话就是将结点的父母和左右子树全置为0.然后将结点1-8的权值先附上的这一步。
第二步：
也就是口诀里的2、选用两小造新树；3、删除两小添新人； 即上述例子里的第二步。
红色框框里的Select() 是选择两个权值最小的结点的函数 具体如下：
void Select(HuffmanTree HT,int len,int &s1,int &s2)
{
int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;//先赋予最大值
for(i=1;i<=len;i++)
{
if(HT[i].weight<min1&&HT[i].parent==0)
{
min1=HT[i].weight;
s1=i;
}
}
int temp=HT[s1].weight;//将原值存放起来，然后先赋予最大值，防止s1被重复选择
HT[s1].weight=0x3f3f3f3f;
for(i=1;i<=len;i++)
{
if(HT[i].weight<min2&&HT[i].parent==0)
{
min2=HT[i].weight;
s2=i;
}
}
HT[s1].weight=temp;//恢复原来的值
}哈弗曼树构造算法实现如下：
void CreatHuffmanTree(HuffmanTree HT,int n){
int(n<=1) return;
m=2*n-1;
HT=new HTNode[m+1];
for(i=1;i<=m;++i){
HT[i].lch=0; HT[i].rch=0; HT[i].parent=0;
}
for(i=1;i<=n;++i) cin>>HT[i].weight;
for(i=n+1;i<=m;i++){
Select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lch=s1; HT[i].rch=s2;
HT[i].weight=HT[s1].weight + HT[s2].weight;
}
}4、哈夫曼树编码思想
上图的编码方式是等长度的，倘如我们使用这种等长度的编码方式，会使得转换的二进制字符串很长，进而浪费更多的空间。所以我们需要使用一种长度不等的编码，这样可以让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少，以达到减少空间的目的。
上图的这种不等长非前缀编码A-0,B-00,C-1,D-01 虽能达到减少转换的二进制字符串长度，但是有一个很致命的问题——重码，就是0000 可以译为AAAA，也可以是ABA，还可以是BB，即它的译码并不唯一。于是我们在不等长编码的基础上使其为前缀的，前缀编码的意思，在一个编码方案中，任一个编码都不是其他任何编码的前缀。
那么什么样的前缀码能使得转换的二进制字符串最短呢？——哈夫曼编码。
其中的重点是将每一个字符出现的频率（即出现的次数）作为权值，构造哈夫曼树，那么就可以达到我们要的目的啦~
举个栗子：
以字符出现频率为权，构造哈弗曼树如上，然之后左分支为0，右分支为1，标出来如下图：
那么就可以知道每个字符的编码啦~
哈夫曼编码的两个性质：
1、哈夫曼编码使前缀码
2、哈夫曼编码使最优前缀码
再举个栗子：
构造哈夫曼树：
所以哈夫曼编码就是这样啦~
5、哈夫曼编码的算法实现。
由上面栗子所构造的哈夫曼树，我们可以写出下面的结构数组。
我们通过这个结构数组来进行叶子结点到根的不断回溯。
例：字符G的编码回溯如下：先在结构数组里找到字符G，然后找G的根结点也就是8，然后在8里看G对应的7是8的左孩子还是右孩子，这里是左孩子，也就是0，然后看8的根结点，也就是10，8是10的左孩子，所以还是0，.......一直循环下去，然后到12的根结点是13，12是13的右孩子，也就是1.接着我们发现13没有了双亲。所以13就是根。那么循环就结束了。所以最后反过来 字符G的二进制就是10000. （ 我们需要用一个数组来储存所得到的0和1，而且需要从尾巴开始储存。 ）
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
HC =new char*[n+1];
cd =new che[n];
cd[n-1]='\0';
for(i=1;i<=n;++i){
start=n-1;c=i;f=HT[i].parent;
while(f!=0){
--start;
if(HT[f].lchild==c) cd[start]='0';
else cd[start]='1';
c=f;f=HT[f].parent;
}
HC[i]=new char[n-start];
strcpy(HC[i],&cd[start]);
}
delete cd;
}
6、文件的编码和译码
举个栗子：
构造哈夫曼树：
按照编码解码：
7、根据哈夫曼树求哈夫曼编码的完整代码：
#include<iostream>
#include<string.h>
using namespace std;
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree HT,int len,int &s1,int &s2)
{
int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;//先赋予最大值
for(i=1;i<=len;i++)
{
if(HT[i].weight<min1&&HT[i].parent==0)
{
min1=HT[i].weight;
s1=i;
}
}
int temp=HT[s1].weight;//将原值存放起来，然后先赋予最大值，防止s1被重复选择
HT[s1].weight=0x3f3f3f3f;
for(i=1;i<=len;i++)
{
if(HT[i].weight<min2&&HT[i].parent==0)
{
min2=HT[i].weight;
s2=i;
}
}
HT[s1].weight=temp;//恢复原来的值
}
//用算法5.10构造赫夫曼树
void CreatHuffmanTree(HuffmanTree &HT,int n)
{
//构造赫夫曼树HT
int m,s1,s2,i;
if(n<=1) return;
m=2*n-1;
HT=new HTNode[m+1]; //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点
for(i=1;i<=m;++i) //将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
{ HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; }
cout<<"请输入叶子结点的权值：\n";
for(i=1;i<=n;++i) //输入前n个单元中叶子结点的权值
cin>>HT[i].weight;
/*――――――――――初始化工作结束，下面开始创建赫夫曼树――――――――――*/
for(i=n+1;i<=m;++i)
{ //通过n-1次的选择、删除、合并来创建赫夫曼树
Select(HT,i-1,s1,s2);
//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,
// 并返回它们在HT中的序号s1和s2
HT[s1].parent=i;
HT[s2].parent=i;
//得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
HT[i].lchild=s1;
HT[i].rchild=s2 ; //s1,s2分别作为i的左右孩子
HT[i].weight=HT[s1].weight+HT[s2].weight; //i 的权值为左右孩子权值之和
} //for
}
// CreatHuffmanTree
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
{
//从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
int i,start,c,f;
HC=new char*[n+1]; //分配n个字符编码的头指针矢量
char *cd=new char[n]; //分配临时存放编码的动态数组空间
cd[n-1]='\0'; //编码结束符
for(i=1;i<=n;++i)
{ //逐个字符求赫夫曼编码
start=n-1; //start开始时指向最后，即编码结束符位置
c=i;
f=HT[i].parent; //f指向结点c的双亲结点
while(f!=0)
{ //从叶子结点开始向上回溯，直到根结点
--start; //回溯一次start向前指一个位置
if(HT[f].lchild==c)
cd[start]='0'; //结点c是f的左孩子，则生成代码0
else
cd[start]='1'; //结点c是f的右孩子，则生成代码1
c=f;
f=HT[f].parent; //继续向上回溯
} //求出第i个字符的编码
HC[i]=new char[n-start]; // 为第i 个字符编码分配空间
strcpy(HC[i], &cd[start]); //将求得的编码从临时空间cd复制到HC的当前行中
}
delete cd; //释放临时空间
} // CreatHuffanCode
void show(HuffmanTree HT,HuffmanCode HC,int n)
{
for(int i=1;i<=sizeof(HC)+1;i++)
cout<<HT[i].weight<<"编码为"<<HC[i]<<endl;
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
int n;
cout<<"请输入叶子结点的个数：\n";
cin>>n; //输入赫夫曼树的叶子结点个数
CreatHuffmanTree(HT,n);
CreatHuffmanCode(HT,HC,n);
show(HT,HC,n);
}
8、 以26个英文字母的频率为权构造一棵哈夫曼树：
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
//哈夫曼树的存储结构
typedef struct
{
char data; //存储数据
int weight; //结点的权重
string num; //存放哈夫曼码
int parent, lchild, rchild; //结点的双亲、左孩子、右孩子的下标
} HTNode,*HuffmanTree;
//两个最小结点
typedef struct
{
int s1;
int s2;
} MIN;
//选择结点权值最小的两个结点
MIN Select(HuffmanTree HT, int n)
{
int min, secmin,s1,s2;
min = 10000;
secmin = 10000;
MIN code;
s1 = 1;
s2 = 1;
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0 && (HT[i].weight<min))
{
min = HT[i].weight;
s1 = i;
}
}
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0 && (HT[i].weight<secmin) && (i != s1))
{
secmin = HT[i].weight;
s2 = i;
}
}
code.s1 = s1;
code.s2 = s2;
return code;
}
//将哈夫曼码存储在结构体num中
void putlorinnum(HuffmanTree &hft, int num)
{
for(int i = num; i >= 1; i--)
{
if(hft[hft[i].parent].parent)
{
hft[i].num = hft[hft[i].parent].num + hft[i].num;
}
}
}
//创造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT, int num)
{
int m;
m = 2 * num - 1;
HT = new HTNode[m + 1]; //分配空间
for (int i = 1; i <= m; i++) //初始化
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
cout << "请输入每个数据及其权值：" << endl;
for (int i = 1; i <= num; i++)
{
cin >> HT[i].weight;
cin>>HT[i].data;
}
for (int i = num + 1; i <= m; i++) //构建哈夫曼树
{
MIN min;
min=Select(HT,i-1); //选择二叉树
HT[min.s1].parent = i;
HT[min.s2].parent = i;
HT[i].lchild = min.s1;
HT[min.s1].num = "0";
HT[i].rchild = min.s2;
HT[min.s2].num = "1";
HT[i].weight = HT[min.s1].weight + HT[min.s2].weight;
HT[i].data = -1;
}
putlorinnum(HT, m);
for (int i = 1; i <= m; i++) //进行每个字符哈夫曼码的输出
{
if(HT[i].data != -1)
{
cout<<HT[i].data<<" 权重为"<<HT[i].weight<<" ，哈夫曼码为："<<HT[i].num<<endl;
cout<<endl;
}
}
}
//将一串字符编译成哈夫曼码
void changchartohft(HuffmanTree hft, string s, int m)
{
string estring;
for(int i = 0;i <= s.size(); i++)
{
for(int x = 1; x <= m; x++)
{
if(hft[x].data == s[i])//查找哈夫曼树中相应的字符
{
estring = estring + hft[x].num;//哈夫曼码连接起来
x = m;
}
}
}
cout<<estring<<endl;
return;
}
//将一串哈夫曼码解译成一串字符
void changhfttochar(HuffmanTree hft, string s, int m)
{
string estring;
int pos = 0, first = 0;
for(int x = 0; x <= s.size(); x++)
{
pos++;
for(int i = 1; i <= m; i++)
{
if(hft[i].num == s.substr(first, pos))//将截取的字符串和哈夫曼中哈夫曼码近行对比
{
cout<<hft[i].data;
first = pos + first;
pos = 0;
}
}
}
cout<<endl;
}
int main()
{
int num; //结点的个数
string s1, s2;
cout << "请输入哈夫曼树叶子结点的个数：";
cin >> num;
//创造哈夫曼树
HuffmanTree HT;
CreateHuffmanTree(HT, num);
while(1)//设置一个循环，可以选择性进行某些步骤。
{
int q;
cout<<"----------------------"<<endl;
cout<<"编译：1"<<endl;
cout<<"解码：2"<<endl;
cout<<"(其他按键结束)"<<endl;
cout<<"输入要进行的操作："<<endl;
cin>>q;
if(q==1)
{
cout<<"输入想要编译的一串字符"<<endl;
cin>>s1;
changchartohft(HT, s1, num);
}
else if(q==2)
{
cout<<"输入想要解码的一串数字"<<endl;
cin>>s2;
changhfttochar(HT, s2, num);
}
else
break;
}
return 0;
}