[二叉树](5)赫夫曼树及其应用
赫夫曼(Huffman)树，又称最优树，是以类带权路径长度最短的树，有着广泛的应用，我们先来讨论最优二叉树
最优二叉树(赫夫曼树)
首先我们需要明确以下几个概念：
路径
- 从树中一个结点到另一个结点之间的分支构成了这两个结点之间的路径
路径长度
- 路径上的分支数目称为路径长度
结点的带权路径长度：
- 是指该结点到树根之间的路径长度与该结点上权的乘积。
权：
- 叶子结点的权值，就是对叶子结点赋予一个有意义的数值量，这个数值量往往体现了访问的频率
二叉树的带权路径长度：
设二叉树具有n个带权值的叶子结点，从跟结点到各个叶子结点的路径长度与相应叶子结点的乘积之和，记作：WPL=(k=1，上限为n)sum:wklk
- wk为第k个结点的权值
- lk为从根结点到第k个叶子的路径长度
假设有n个权值{w1,w2,w3,...,wn}构成一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称作最优二叉树或赫夫曼树
例如，下图中的3课二叉树，都有四个结点a，b，c，d，分别带权7、5、2、4，它们的带权路径长度分别为：
具有不同带权路径长度的二叉树
- WPL=7*2 + 5*2 + 2*2 + 4*2 = 36
- WPL=7*3 + 5*3 + 2*1 + 4*2 = 46
- WPL=7*1 + 5*2 + 2*3 + 4*3 = 35
对这里不太理解的可以看：
我们用第三棵树来做个讲解：
其中以(3)树为最小，可以验证，它恰为赫夫曼树，则其带权路径长度在所有带权为7、5、2、4的4个叶子结点的二叉树中居最小.
从上述我们可以知道赫夫曼树的特点如下：
权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点
- 为了能够让带权路径最小，则我们需要将最大的带权叶子结点(上述为a)离根最近，而权值最小的(上述为c，d)离叶子结点最远
- 只有度为0(叶子结点)和度为2(分支结点)的结点，不存在度为1的结点
为了更好的理解赫夫曼树，我们看看下面这个例子：
在解某些判断问题时，利用赫夫曼树可以得到最佳判定的算法，例如，要编制一个将百分制换成五级分制的程序，显然，此程序很简单，只要利用条件语句便可完成，如：
if(a < 60) b="bad";
else if(a < 70） b="pass";
else if(a < 80) b="general";
else if(a < 90) b="good";
else b ="excellent"如果上述程序需要反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需时间，因为在实际生活中，学生的成绩在5个等级上的分布是不均匀的，假设其分布规律如下表所示：
则百分之八十以上的数据都需要进行3次或三次以上的比较才能得出结果，假定以5、15、40、30和10为权构造一棵有5个叶子结点的赫夫曼树，则可得到下面两种形式的判定，树：
假定有10000个输入数据，若按上图的判定过程进行操作，则总共需要进行31500次比较，而若按下图的判定过程进行操作，则只需要比较22000次
显然，第二种赫夫曼树形式的判定树效率最高。
那么，如何构造赫夫曼树呢？赫夫曼最早给出了一个带有一般规律的算法，俗称赫夫曼算法：
- 初始化：根据给定的n个权值{W1,W2,W3....,Wn}构成n棵二叉树的集合F={T1,T2,...,Tn}
- 选择与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵二叉树的根结点的权值为其左、右子树根结点的权值之和
- 删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中
- 重复(2)、(3)两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是赫夫曼树
动画演示如下：如果不太了解可以看上述视频讲解，懒猫老师讲的通俗易懂。
<video controls="" src="https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/Create_Huffman.mp4";></video>
赫夫曼树的存储结构
综上所述，我们很容易就可以确定对于赫夫曼树的最优存储结构：
- 需要知道双亲信息
- 需要知道孩子信息
- 需要多次合并结点
- 需要多次改变结点信息
这四个一下来，只有顺序存储最合适了，我们采用一个结构数组来做存储，而这个数组的大小即为2n-1(n为给定权值的叶子结点个数)
为什么会是2n-1个呢？我们来复习以下二叉树的性质三：
而为了便于理解，我们不使用0下标，直接使用1下标，即数组大小需为2n。
赫夫曼编码
赫夫曼树的主要应用，就是用于赫夫曼编码，我们先了解下述概念：
- 给每一个对象标记一个二进制位串来表示一组对象，例：ASCII、指令系统
编码分类：
等长编码：表示一组对象的二进制位串的长度相等
- 等长编码长度较短时，空间效率最高
不等长编码：表示一组对象的二进制位串的长度不相等
- 出现频率比较高的对象，采用短的编码，出现频率比较低的对象，我们采用长的编码，这样空间效率最高
目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转换由二进制的字符组成的字符串，例如，假设需传送的电文为"A B A C C D ",它只有四种字符，只需要两个字符的串并可分辨，假设A、B、C、D的编码分别为00、01、10和11，则上述7个字符的电文便为："00010010101100"总长14位，对方接收时，可按二位一分进行解码
当然，在传送电文时，希望总长尽可能短，则传送电文的总长便可减少，如果设计A、B、C、D的编码分别为0、00、1和01，则上述7个字符的电文可转换成总长为9的字符串'000011010'，但是，这样的电文无法翻译
例如传送过去的字符串中前4个字符的子串'0000'就可以有多种译法，或是AAAA还可以是ABA也可以是BB等，因此，若要设计长短不等的编码，则必须是任一个字符的编码，都不是另一个字符的编码的前缀，这种编码称作前缀编码
这样就保证了不等长编码的解码唯一性，而赫夫曼编码，就是一种前缀编码，因此Heffman编码保证了解码的唯一性。
如下图所示的二叉树，其4个叶子结点分别表示A、B、C、D这四个字符，且约定左分支表示字符'0'，右分支表示字符'1’,则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点的字符编码
前缀编码示例
可以证明，如此得到的必为二进制前缀编码。
又如何得到使电文总长最短的二进制前缀编码呢？假设每种字符在电文中出现的次数位wi，其编码长度为L，电文中只有n种字符，则电文总长为sum(上界为n，i=1)wili
对应到二叉树上，若置wi为叶子结点的权，Li恰好为从根到叶子的路径长度，则sum(上界为n，i=1)wili恰为二叉树上带权路径长度，由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权
设计一棵赫夫曼编码的问题，由此得到二进制的前缀编码便称为赫夫曼编码。
由于二叉树种没有度为1的结点，是一棵完满二叉树，则一棵又n个结点的赫夫曼树共又2n-1个结点。
为了便于操作，我们让0单元不用，可以存储到2n的结构数组中，而建造赫夫曼树又需要知道双亲的信息和孩子的信息，则最合适的就是顺序存储。如下所示：
//赫夫曼树和赫夫曼编码的存储表示
typedef char** HuffmanCode;//动态分配数组存储赫夫曼编码表
typedef struct Huffman
{
int weight;
int parent;
int lchild;
int rchild;
}Huffman, * HuffmanTree;//动态分配数组存储赫夫曼树求赫夫曼编码的算法如下所示：
Status InitHuffmanTree(HuffmanTree* H, int n, WeightNode N) {
//n 为权值
int m = 2 * n;
if (!((*H) = (HuffmanTree)malloc(sizeof(Huffman) * m)))return ERROR;
for (int i = 1; i < m; i++) {//0号单元未使用
(*H)[i].weight = -1;
(*H)[i].data = '#';
if (i <= n) {//在初始化的时候将给定的叶子结点赋予权值
//创建n个根结点
(*H)[i].data = N.SW[i - 1].key;
(*H)[i].weight = N.SW[i - 1].val;
}
(*H)[i].parent = -1; (*H)[i].rchild = -1; (*H)[i].lchild = -1;
}
return OK;
}
Status Select_Min(HuffmanTree H, int* i, int* j, int n) {
int Min1 = INT_MAX;
int Min2 = Min1;
int p = 1;
while (p < n) {
if (H[p].parent == -1 && H[p].weight < Min2) {
Min1 = Min2;
Min2 = H[p].weight;
*i = *j;
*j = p;
}
else if (H[p].parent == -1 && H[p].weight < Min1) {
Min1 = H[p].weight;
*i = p;
}
p++;
}
return OK;
}
Status CreateHuffmanTree(HuffmanTree H, int n) {
int m = 2 * n;
int k = 1;
int i, j;
int Index = n + 1;
while (Index < m) {
Select_Min(H, &i, &j, Index);
printf("次小值：%d,最小值：%d\n", i, j);
H[i].parent = Index;
H[j].parent = Index;
H[Index].weight = H[i].weight + H[j].weight;
H[Index].lchild = i;
H[Index].rchild = j;
Index++;
k++;
}
Print_HuffMap(H, m);
return OK;
}从叶子到根逆向求每个字符的赫夫曼编码算法如下所示：
//HuffmanCode为char**
Status HuffmanCode_leaf(HuffmanTree H, HuffmanCode* cd, int n) {
*cd = (char**)malloc(sizeof(char*) * n);//创建每一个字符的赫夫曼编码
char* TempCode = (char*)malloc(sizeof(char) * n);
int start = n;
TempCode[--start] = '\0';//在尾部赋空字符
int j = 0, i = 1;
while (i <= n) {
int p = i;
while (H[p].parent != -1) {
int p1 = p;
p = H[p].parent;
if (H[p].lchild == p1) {
TempCode[--start] = '0';
}
else if (H[p].rchild == p1) {
TempCode[--start] = '1';
}
}
(*cd)[j] = (char*)malloc(sizeof(char) * (n - start));
StrCopy((*cd)[j], TempCode, start, n);
start = n - 1;
i++;
j++;
}
Print_HuffmanCode(*cd, n);
return OK;
}向量H的前n个分量表示叶子结点，最后一个分量表示根结点，各字符长度不等，所以按实际长度动态分配空间，在上述算法中，求每个字符的赫夫曼编码是从叶子到根逆向处理的
当然，也可以从根出发，遍历整棵赫夫曼数，求得各个叶子结点所表示的字符的赫夫曼编码，对于从根出发求赫夫曼编码，只用于了解赫夫曼树的特性，在这里便不推荐各位使用，我们可以知道：
- 赫夫曼树是一棵完满二叉树，它只有度为0或度为2的结点，则我们可通过是否存在左子树来判断是否为叶子结点
- 则若左子树为空的情况，就代表找到了叶子节点，可求得编码
- 上一步完后，还需要退回它的父结点去探寻右子树
如上所示，乍一看是否有点像二叉树的中序遍历，算法如下所示：
Status HuffmanCode_root(HuffmanTree H, HuffmanCode* cd, int n) {
int m = 2 * n - 1;
(*cd) = (HuffmanCode)malloc(sizeof(char*) * (n * 1));
char* tempCode = (char*)malloc(sizeof(char) * (n + 1));
int p = m;
int cdlen = 0;
for (int i = 1; i <= m; i++) H[i].weight = 0;//遍历赫夫曼树时用作结点状态标志
while (p) {
if (H[p].weight == 0) {//向左探寻
H[p].weight = 1;
if (H[p].lchild != -1) {
p = H[p].lchild;
tempCode[cdlen++] = '0';
}
else if (H[p].rchild == -1) {//登记叶子结点的字符编码
cd[p] = (char*)malloc(sizeof(char) * (cdlen + 1));
tempCode[cdlen] = "\0";
strcpy(cd[p], tempCode);
}//复制编码
}
else if (H[p].weight == 1) {//向右
H[p].weight = 2;
if (H[p].rchild != -1) {
p = H[p].rchild;
tempCode[cdlen++] = "1";
}
else {
H[p].weight = 0;
p = H[p].parent;//退回父结点
--cdlen;//编码长度减一
}
}
}
return OK;
}从上述算法我们可以看到，需要修改权值域来做遍历时的结点标志域，这样做的弊端是会打乱创建好的赫夫曼树。
下面给出详细可执行代码，功能为：
- 给定一个字符串，创建其权值表
- 通过权值表创建其huffman树
- 通过huffman树解码和加密
#define _CRT_SECURE_NO_WARNINGS
#define OK 1
#define ERROR 0
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Huffman {
char data;
int weight;
int parent, lchild, rchild;
}Huffman,*HuffmanTree;
/*用于存储字符串生成的赫夫曼编码*/
typedef struct StrNode {
char key;//字符
int val;//出现频率
}*StrLink, StrNode;
typedef struct WeightNode {
StrLink SW;
int len;
}WeightNode;
typedef struct StrCd {
char key;//字符
char* val;//对应赫夫曼编码
}*StrCode, StrCodeNode;
typedef struct StrCodeLink {
StrCode C;
int len;
}*StrCodeList,StrCodeLink;
typedef char** HuffmanCode; //赫夫曼树存储模式
typedef char String[255];//字符串
typedef int Status;
typedef int Bool;
Status Print_HuffMap(HuffmanTree H, int n);//打印赫夫曼树存储表
Status InitHuffmanTree(HuffmanTree* H, int n, WeightNode N);//初始化赫夫曼树，约定如下：
//1、权值，孩子，双亲全部初始化负一
//2、WeightNode类型为叶子结点Data和给定权值
//3、n为叶子结点个数
//4、从1开始，不使用0位置
Status CreateHuffmanTree(HuffmanTree H, int n);//根据给定权值创建完整的赫夫曼树，约定如下：
Status Select_Min(HuffmanTree H, int* i, int* j, int n);//找两个权值最小的叶子结点，约定如下：
//1、i为次小值下标，j为最小值下标
Status StrCopy(char* a, char* b, int start, int end);//从给定位置将b复制为a
Status Print_HuffmanCode(HuffmanCode cd, int n);//打印结点对应的赫夫曼编码
Status HuffmanCode_leaf(HuffmanTree H, HuffmanCode* cd, int n);//对赫夫曼树从叶子结点获取赫夫曼编码
Status EncrStrCode(String S, StrCodeList SD);//加密给定字符串
Status StrHuffmanTree(String S, HuffmanTree* H);//对给定字符串生成其赫夫曼树
int main()
{
int n;
HuffmanTree H;
HuffmanCode cd = NULL;
printf("输入一字符串输出其二进制编码，约定左子树为0右子树为1：");
String S;
HuffmanTree HT;
gets(S);
StrHuffmanTree(S, &HT);
system("pause");
return 0;
}
Status InitHuffmanTree(HuffmanTree* H, int n, WeightNode N) {
//n 为权值
int m = 2 * n;
if (!((*H) = (HuffmanTree)malloc(sizeof(Huffman) * m)))return ERROR;
for (int i = 1; i < m; i++) {//0号单元未使用
(*H)[i].weight = -1;
(*H)[i].data = '#';
if (i <= n) {//在初始化的时候将给定的叶子结点赋予权值
//创建n个根结点
(*H)[i].data = N.SW[i - 1].key;
(*H)[i].weight = N.SW[i - 1].val;
}
(*H)[i].parent = -1; (*H)[i].rchild = -1; (*H)[i].lchild = -1;
}
return OK;
}
Status Select_Min(HuffmanTree H, int* i, int* j, int n) {
int Min1 = INT_MAX;
int Min2 = Min1;
int p = 1;
while (p < n) {
if (H[p].parent == -1 && H[p].weight < Min2) {
Min1 = Min2;
Min2 = H[p].weight;
*i = *j;
*j = p;
}
else if (H[p].parent == -1 && H[p].weight < Min1) {
Min1 = H[p].weight;
*i = p;
}
p++;
}
return OK;
}
Status CreateHuffmanTree(HuffmanTree H, int n) {
int m = 2 * n;
int k = 1;
int i, j;
int Index = n + 1;
while (Index < m) {
Select_Min(H, &i, &j, Index);
printf("次小值：%d,最小值：%d\n", i, j);
H[i].parent = Index;
H[j].parent = Index;
H[Index].weight = H[i].weight + H[j].weight;
H[Index].lchild = i;
H[Index].rchild = j;
Index++;
k++;
}
Print_HuffMap(H, m);
return OK;
}
Status Print_HuffMap(HuffmanTree H, int n) {
int i = 1;
printf("Data\tWieght\tparent\tlchild\trchild\n");
while (i < n) {
printf("%c\t%d\t%d\t%d\t%d\n", H[i].data, H[i].weight, H[i].parent, H[i].lchild, H[i].rchild);
i++;
}
printf("=================================\n");
return OK;
}
Status StrCopy(char* a, char* b, int start, int end) {
int j = 0;
while (start < end) {
a[j] = b[start];
start++;
j++;
}
a[j] = '\0';
return OK;
}
Status Print_HuffmanCode(HuffmanCode cd, int n) {
int i = 0;
while (i < n) {
printf("%s\n", cd[i]);
i++;
}
printf("=================================\n");
return OK;
}
Status HuffmanCode_leaf(HuffmanTree H, HuffmanCode* cd, int n) {
*cd = (char**)malloc(sizeof(char*) * n);
char* TempCode = (char*)malloc(sizeof(char) * n);
int start = n;
TempCode[--start] = '\0';
int j = 0, i = 1;
while (i <= n) {
int p = i;
while (H[p].parent != -1) {
int p1 = p;
p = H[p].parent;
if (H[p].lchild == p1) {
TempCode[--start] = '0';
}
else if (H[p].rchild == p1) {
TempCode[--start] = '1';
}
}
(*cd)[j] = (char*)malloc(sizeof(char) * (n - start));
StrCopy((*cd)[j], TempCode, start, n);
start = n - 1;
i++;
j++;
}
Print_HuffmanCode(*cd, n);
return OK;
}
Status PretHuffmanCode(HuffmanCode cd, HuffmanTree H, int n, StrCodeList* SD) {
int f;
(*SD) = (StrCodeList)malloc(sizeof(StrCodeLink));
(*SD)->len = 0;
(*SD)->C = (StrCode)malloc(sizeof(StrCodeNode) * n);
for (int i = 0; i < n; i++) {
int j = 0;
f = 2 * n - 1;
while (cd[i][j] != '\0') {
if (cd[i][j] == '0')
f = H[f].lchild;
else
f = H[f].rchild;
j++;
}
printf("%s is translated into %c\n", cd[i], H[f].data);
(*SD)->C[(*SD)->len].val = (char*)malloc(sizeof(char));
strcpy((*SD)->C[(*SD)->len].val, cd[i]);
(*SD)->C[(*SD)->len].key = H[f].data;
(*SD)->len++;
}
printf("=================================\n");
return OK;
}
Status EncrStrCode(String S, StrCodeList SD) {
char* StrCode = (char*)malloc(sizeof(char) * SD->len * SD->len);
int p = 0;
for (int i = 0; i < strlen(S); i++) {
int j = 0;
while (j < SD->len) {
if (SD->C[j].key == S[i]) {
int k = 0;
while (SD->C[j].val[k] != '\0') {
StrCode[p] = SD->C[j].val[k];
k++;
p++;
}
StrCode[p] = ' ';
p++;
}
j++;
}
}
StrCode[p] = '\0';
printf("\nStr'HuffmanCode：%s\n", StrCode);
printf("=================================\n");
return OK;
}
Status StrHuffmanTree(String S, HuffmanTree* H) {
int sleng = strlen(S);
char* w = (char*)malloc(sizeof(char) * sleng);
int flag;
WeightNode N;
N.SW = (StrLink)malloc(sizeof(StrNode) * sleng);
N.len = 0;
for (int i = 0; i < sleng; i++) {
int j = 0; flag = 0;
while (j < N.len) {
if (S[i] == N.SW[j].key) {
flag = 1;
N.SW[j].val++;
break;
}
j++;
}
if (!flag) {
N.SW[N.len].key = S[i];
N.SW[N.len].val = 1;
N.len++;
}
}
HuffmanCode cd = NULL;
StrCodeList SD = NULL;
InitHuffmanTree(H, N.len, N);//初始化赫夫曼树
CreateHuffmanTree(*H, N.len);//创建赫夫曼树
HuffmanCode_leaf(*H, &cd, N.len);//从叶子结点解码
PretHuffmanCode(cd, *H, N.len, &SD);//解密字符串
EncrStrCode(S, SD);//加密字符串
return OK;
}