哈夫曼树的基本概念
哈夫曼树（Huffman Tree）是一种用于数据压缩的最优二叉树，广泛应用于哈夫曼编码中。其基本概念和构建方法如下：
基本概念
- 二叉树：哈夫曼树是一种特殊的二叉树。
- 权重：每个节点都有一个权重，通常是字符或数据出现的频率。
- 路径长度：从根节点到某一节点的路径长度称为该节点的路径长度。
- 带权路径长度：节点的路径长度乘以该节点的权重。
- 树的带权路径长度：树中所有叶子节点的带权路径长度之和。哈夫曼树的带权路径长度是最小的。
1.什么是路径？
在一棵树中，从一个节点往下可以达到的节点之间的通路，称为路径。
如图，从根节点7到叶子节点a的路径就是7->3->1->a
2.什么是路径长度
某一路径所经过的“边”的数量，称为该路径的路径长度
对于字符'a'，路径长度是指从根节点到字符'a'节点的边的数量。在这个示例中，路径长度为3，因为从根节点到字符'a'节点有三条边。
对于字符'b'，路径长度也是指从根节点到字符'b'节点的边的数量。在这个示例中，路径长度为3，因为从根节点到字符'b'节点有三条边。
3.什么是节点的带权路径长度？
节点的权通常是指节点所代表的字符在数据中出现的频率或权重。从根结点到该结点之间的路径长度与该结点的节的乘积，称为该结点的带权路径长度。
假设树中的叶节点a代表字符'a'，并且字符'a'在数据中出现了3次；叶节点b代表字符'b'，字符'b'在数据中出现了3次；叶节点c代表字符'c'，字符'c'在数据中出现了3次；叶节点d代表字符'd'，字符'd'在数据中出现了3次；叶节点e代表字符'e'，字符'e'在数据中出现了3次；叶节点f代表字符'f'，字符'f'在数据中出现了3次；叶节点g代表字符'g'，字符'g'在数据中出现了4次。
根据定义，每个节点的带权路径长度是从根节点到该节点的路径长度与该节点的权的乘积。
现在让我们计算加权路径长度：
- 根节点的带权路径长度为 0（根节点）乘以 13（根节点权）= 0。
- 节点 a 的带权路径长度为 3（根节点到节点a的路径长度）乘以 3（节点 a 的权重）= 9。
- 节点 b 的带权路径长度为 3（根节点到节点b的路径长度）乘以 3（节点 b 的权重）= 9。
- 节点 c 的带权路径长度为 3（根节点到节点c的路径长度）乘以 3（节点 c 的权重）= 9。
- 节点 d 的带权路径长度为 3（根节点到节点d的路径长度）乘以 3（节点 d 的权重）= 9。
- 节点 e 的带权路径长度为 3（根节点到节点e的路径长度）乘以 3（节点 e 的权重）= 9。
- 节点 f 的带权路径长度为 3（根节点到节点f的路径长度）乘以 3（节点 f 的权重）= 9。
- 节点 g 的带权路径长度为 3（根节点到节点g的路径长度）乘以 4（节点 g 的权重）= 12。
什么是树的带权路径长度？
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
假设树中的叶节点a代表字符'a'，并且字符'a'在数据中出现了3次；叶节点b代表字符'b'，字符'b'在数据中出现了3次；叶节点c代表字符'c'，字符'c'在数据中出现了3次；叶节点d代表字符'd'，字符'd'在数据中出现了3次；叶节点e代表字符'e'，字符'e'在数据中出现了3次；叶节点f代表字符'f'，字符'f'在数据中出现了3次；叶节点g代表字符'g'，字符'g'在数据中出现了4次。
如图，该二叉树的带权路径长度 WPL= 0 + 4 + 8 + 9 + 8 + 8 + 17 + 12 = 66。
5、什么是哈夫曼树
给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称该二叉树为哈夫曼树，也被称为最优二叉树。
根据树的带权路径长度的计算规则，我们不难理解：树的带权路径长度与其叶子结点的分布有关。
即便是两棵结构相同的二叉树，也会因为其叶子结点的分布不同，而导致两棵二叉树的带权路径长度不同。
那如何才能使一棵二叉树的带权路径长度达到最小呢？
根据树的带权路径长度的计算规则，我们应该尽可能地让权值大的叶子结点靠近根结点，让权值小的叶子结点远离根结点，这样便能使得这棵二叉树的带权路径长度达到最小。
哈夫曼树的创建
构建思路
下面给出一个非常简洁易操作的算法，来构造一棵哈夫曼树：
1、初始状态下共有n个结点，结点的权值分别是给定的n个数，将他们视作n棵只有根结点的树。
2、合并其中根结点权值最小的两棵树，生成这两棵树的父结点，权值为这两个根结点的权值之和，这样树的数量就减少了一个。
3、重复操作2，直到只剩下一棵树为止，这棵树就是哈夫曼树。
动图演示:
我们展现一个简单一点的哈夫曼树的形成过程
假设有以下字符及其频率
首先，我们将字符及其频率表示为叶子节点：
然后，我们将这些叶子节点放入一个优先队列（按频率升序排列）：
接下来，我们开始合并节点，每次合并都是取出频率最小的两个节点并创建一个新的节点，然后将新节点放回队列中：
第一步合并 (a,5) 和 (b,9)，得到新节点 (ab,14)：
第二步合并 (c,12) 和 (d,13)，得到新节点 (cd,25)：
第三步合并 (ab,14) 和 (e,16)，得到新节点 (abe,30)：
第四步合并 (f,45) 和 (cd,25)，得到新节点 (fcd,70)：
最后，合并 (abe,30) 和 (fcd,70)，得到根节点：
这样，我们就构建了哈夫曼树。从根节点到叶子节点的路径就是字符的哈夫曼编码，频率越高的字符路径越短。
代码展示
// 定义节点结构体
typedef struct Node {
int freq; // 节点频率
char data; // 节点字符数据
struct Node *left; // 左子节点指针
struct Node *right;// 右子节点指针
} Node;
// 创建新节点
Node* createNode(int freq, char data) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 分配节点内存空间
newNode->freq = freq; // 设置节点频率
newNode->data = data; // 设置节点字符数据
newNode->left = NULL; // 左子节点初始化为空
newNode->right = NULL; // 右子节点初始化为空
return newNode; // 返回新节点指针
}
// 构建哈夫曼树
Node* buildHuffmanTree(char data[], int freq[], int size) {
// 创建叶子节点数组
Node* leafNodes[size];
for (int i = 0; i < size; i++) {
leafNodes[i] = createNode(freq[i], data[i]);
}
// 构建哈夫曼树
while (size > 1) {
// 找到频率最小的两个节点
int min1 = 0, min2 = 1;
if (leafNodes[min1]->freq > leafNodes[min2]->freq) {
int temp = min1;
min1 = min2;
min2 = temp;
}
for (int i = 2; i < size; i++) {
if (leafNodes[i]->freq < leafNodes[min1]->freq) {
min2 = min1;
min1 = i;
} else if (leafNodes[i]->freq < leafNodes[min2]->freq) {
min2 = i;
}
}
// 创建新节点作为合并结果
Node* newNode = createNode(leafNodes[min1]->freq + leafNodes[min2]->freq, '$');
newNode->left = leafNodes[min1];
newNode->right = leafNodes[min2];
// 从叶子节点数组中移除被合并的节点，将新节点加入数组
leafNodes[min1] = newNode;
leafNodes[min2] = leafNodes[size - 1];
size--;
}
// 返回根节点
return leafNodes[0];
}
哈夫曼编码的生成
编码生成思路
对于任意一棵二叉树来说，把二叉树上的所有分支都进行编号，将所有左分支都标记为0，所有右分支都标记为1。
我们就以7、5、4、2构建的哈夫曼树为例。
那么对于树上的任何一个结点，都可以根据从根结点到该结点的路径唯一确定一个编号。
对于哈夫曼树上的叶子结点，根据从根结点到该叶子结点的路径所确定的一个编号，就是该叶子结点的哈夫曼编码。
代码实现
我们首先需要清楚这样一个问题：
用n个数据所构建出来的哈夫曼树，生成的哈夫曼编码的长度最长是多少？
因为哈夫曼编码是根据从根结点到该叶子结点的路径所确定的一个编号，所以生成的哈夫曼编码最长的叶子结点一定是离根结点最远的结点。要使叶子结点里根结点达到最远，那么生成的哈夫曼树应该是斜二叉树。
该斜二叉树中最后一层的叶子结点所生成的哈夫曼编码就是最长的，其哈夫曼编码的长度就是从根结点到达该叶子结点的路径长度，即n − 1 n-1n−1。
一个字符串若是想要容纳下“用n个数据生成的哈夫曼编码”中的任意一个编码，那么这个字符串的长度应该为n nn，因为我们还需要用一个字节的位置用于存放字符串的结束标志’\0’。
我们就以数字7、5、4、2构建的哈夫曼树为例，哈夫曼编码生成的基本实现步骤如下：
第一阶段：
因为数据个数为4，所以我们开辟一个大小为4的辅助空间，并将最后一个位置赋值为’\0’，用于暂时存放正在生成的哈夫曼编码。
为了存放这4个数据哈夫曼编码，我们开辟一个字符指针数组，该数组中有5个元素，每个元素的类型为char**，该字符指针数组的基本布局如下：
注意：这里为了与“构建哈夫曼树时所生成的数组”中的下标相对应，所以该字符指针数组中下标为0的元素也不存储有效数据。
第二阶段：
利用已经构建好的哈夫曼树，生成这4个数据的哈夫曼编码。单个数据生成哈夫曼编码的过程如下：
1、判断该数据结点与其父结点之间的关系，若该数据结点是其父结点的左孩子，则将start指针前移，并将0填入start指向的位置，若是右孩子，则在该位置填1。
2、接着用同样的方法判断其父结点与其父结点的父结点之间的关系，直到待判断的结点为哈夫曼树的根结点为止，该结点的哈夫曼编码生成完毕。
3、将字符串中从start的位置开始的数据拷贝到字符指针数组中的相应位置。
注意：在每次生成数据的哈夫曼编码之前，先将start指针指向’\0’。
按照此方式，依次生成7、5、4、2的哈夫曼编码后，字符指针数组的基本布局如下：
哈夫曼编码生成完毕。
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef double DataType; //结点权值的数据类型
typedef struct HTNode //单个结点的信息
{
DataType weight; //权值
int parent; //父节点
int lc, rc; //左右孩子
}*HuffmanTree;
typedef char **HuffmanCode; //字符指针数组中存储的元素类型
//在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1的权值小于s2的权值
void Select(HuffmanTree& HT, int n, int& s1, int& s2)
{
int min;
//找第一个最小值
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0)
{
min = i;
break;
}
}
for (int i = min + 1; i <= n; i++)
{
if (HT[i].parent == 0 && HT[i].weight < HT[min].weight)
min = i;
}
s1 = min; //第一个最小值给s1
//找第二个最小值
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0 && i != s1)
{
min = i;
break;
}
}
for (int i = min + 1; i <= n; i++)
{
if (HT[i].parent == 0 && HT[i].weight < HT[min].weight&&i != s1)
min = i;
}
s2 = min; //第二个最小值给s2
}
//构建哈夫曼树
void CreateHuff(HuffmanTree& HT, DataType* w, int n)
{
int m = 2 * n - 1; //哈夫曼树总结点数
HT = (HuffmanTree)calloc(m + 1, sizeof(HTNode)); //开m+1个HTNode，因为下标为0的HTNode不存储数据
for (int i = 1; i <= n; i++)
{
HT[i].weight = w[i - 1]; //赋权值给n个叶子结点
}
for (int i = n + 1; i <= m; i++) //构建哈夫曼树
{
//选择权值最小的s1和s2，生成它们的父结点
int s1, s2;
Select(HT, i - 1, s1, s2); //在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1的权值小于s2的权值
HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权重是s1和s2的权重之和
HT[s1].parent = i; //s1的父亲是i
HT[s2].parent = i; //s2的父亲是i
HT[i].lc = s1; //左孩子是s1
HT[i].rc = s2; //右孩子是s2
}
//打印哈夫曼树中各结点之间的关系
printf("哈夫曼树为:>\n");
printf("下标 权值 父结点 左孩子 右孩子\n");
printf("0 \n");
for (int i = 1; i <= m; i++)
{
printf("%-4d %-6.2lf %-6d %-6d %-6d\n", i, HT[i].weight, HT[i].parent, HT[i].lc, HT[i].rc);
}
printf("\n");
}
//生成哈夫曼编码
void HuffCoding(HuffmanTree& HT, HuffmanCode& HC, int n)
{
HC = (HuffmanCode)malloc(sizeof(char*)*(n + 1)); //开n+1个空间，因为下标为0的空间不用
char* code = (char*)malloc(sizeof(char)*n); //辅助空间，编码最长为n(最长时，前n-1个用于存储数据，最后1个用于存放'\0')
code[n - 1] = '\0'; //辅助空间最后一个位置为'\0'
for (int i = 1; i <= n; i++)
{
int start = n - 1; //每次生成数据的哈夫曼编码之前，先将start指针指向'\0'
int c = i; //正在进行的第i个数据的编码
int p = HT[c].parent; //找到该数据的父结点
while (p) //直到父结点为0，即父结点为根结点时，停止
{
if (HT[p].lc == c) //如果该结点是其父结点的左孩子，则编码为0，否则为1
code[--start] = '0';
else
code[--start] = '1';
c = p; //继续往上进行编码
p = HT[c].parent; //c的父结点
}
HC[i] = (char*)malloc(sizeof(char)*(n - start)); //开辟用于存储编码的内存空间
strcpy(HC[i], &code[start]); //将编码拷贝到字符指针数组中的相应位置
}
free(code); //释放辅助空间
}
//主函数
int main()
{
int n = 0;
printf("请输入数据个数:>");
scanf("%d", &n);
DataType* w = (DataType*)malloc(sizeof(DataType)*n);
if (w == NULL)
{
printf("malloc fail\n");
exit(-1);
}
printf("请输入数据:>");
for (int i = 0; i < n; i++)
{
scanf("%lf", &w[i]);
}
HuffmanTree HT;
CreateHuff(HT, w, n); //构建哈夫曼树
HuffmanCode HC;
HuffCoding(HT, HC, n); //构建哈夫曼编码
for (int i = 1; i <= n; i++) //打印哈夫曼编码
{
printf("数据%.2lf的编码为:%s\n", HT[i].weight, HC[i]);
}
free(w);
return 0;
}
