1. 概念
哈夫曼树，即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。
在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。
1.1 构建过程
哈夫曼树的构建过程：
每次在所有未使用结点(白底)中先找到最小的两个(红底)，然后构建一个双亲节点指向他们。
哈弗曼树的构建过程
2. 实现
2.1 结构
因为知道叶子节点个数，可以推算出总体的结点个数。使用顺序存储方式，使用索引访问更方便。
设叶子结点有个，度为1的结点有
个，度为2的结点有
个。每个结点都是双亲节点的度，根结点除外，所以用度计算总结点数为
。
哈夫曼数中，不存在度为1的节点，即：
// 构建哈弗曼树的结点
typedef struct HaffNode {
int weight; // 权值
int flag; // 是否使用过
int parent; // 父节点索引
int leftChild; // 左儿子索引
int rightChild; // 右儿子索引
} HaffNode;
// 存放哈夫曼编码的数据元素结构
typedef struct Code {
int bit[MaxBit]; // 固定大小的数组
int length; // 编码的长度
int weight; // 字符的权值
} Code;
2.2 构建哈夫曼树
// 1.根据权重值，构建哈夫曼树
// {2,4,5,7} n=4
void Haffman(int *weight, int n, HaffNode *haffTree) {
/*
1.初始化
设叶子结点有n个，度为1的结点有x个，度为2的结点有y个
每个结点都是双亲节点的度，根结点除外，所以用度计算总结点数为x + 2 * y + 1
x + 2 * y + 1 = n + x + y => y = n - 1
哈夫曼数中，不存在度为1的节点，n + x + y = n + y = 2n - 1
*/
for (int i = 0; i < 2*n-1; i++) {
if (i < n) {
haffTree[i].weight = weight[i]; // 有权值的叶子节点
} else {
haffTree[i].weight = 0; // 非叶子节点
}
// 其他属性初始化
haffTree[i].flag = 0;
haffTree[i].parent = haffTree[i].leftChild = haffTree[i].rightChild = -1;
}
// 2.构建哈夫曼树
int m1,m2; // 记录最小的两个值
int x1,x2; // 最小两个值的索引
// 总结点数2n-1，我们要构建的双亲节点只有2n-1 - n = n-1个
for (int i = 0; i < n - 1; i++) {
m1 = m2 = MaxValue; // 先赋值为最大值，然后找更小的值，后续存储m1<m2
x1 = x2 = 0; // 索引重置
// 循环找出所有权重中，最小的二个值
// 因为添加了新的双亲结点，所以遍历长度会增加
for (int j = 0; j< n + i; j++) {
if (haffTree[j].weight < m1 && haffTree[j].flag == 0) { // cur<m1<m2
m2 = m1;
x2 = x1;
m1 = haffTree[j].weight;
x1 = j;
} else if(haffTree[j].weight < m2 && haffTree[j].flag == 0) { // m1<cur<m2
m2 = haffTree[j].weight;
x2 = j;
}
}
// 3.将找出的两棵权值最小的子树合并为一棵子树
// 标记两个结点已使用
haffTree[x1].flag = 1;
haffTree[x2].flag = 1;
// 存储双亲结点索引
haffTree[x1].parent = n + i;
haffTree[x2].parent = n + i;
// 设置双亲结点
haffTree[n + i].leftChild = x1;
haffTree[n + i].rightChild = x2;
// 计算双亲结点的权值
haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
}
}
2.3 构建哈夫曼编码数组
/*
2.哈夫曼编码
由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
//{2,4,5,7}
*/
void HaffmanCode(HaffNode *haffTree, int n, Code *haffCode) {
// 1.创建一个结点cd，辅助存储信息
Code cd;
int child, parent;
// 2.求n个叶结点的哈夫曼编码
for (int i = 0; i < n; i++) {
cd.length = 0; // 从0开始计数
cd.weight = haffTree[i].weight; // 取得编码对应权值的字符
child = i; // 设置当前叶子结点为孩子
parent = haffTree[child].parent; // 找到叶子节点的双亲结点
// 因为起点我们只能从叶子节点开始，向上查找
while (parent != -1) { // 通过-1判断是否还有双亲结点
if (haffTree[parent].leftChild == child) // 判断当前结点是左孩子还是右孩子
cd.bit[cd.length] = 0; // 左孩子结点编码0
else
cd.bit[cd.length] = 1; // 右孩子结点编码1
cd.length++; // 编码长度自增
child = parent; // 当前双亲结点成为孩子结点，继续向上查找
parent = haffTree[child].parent; // 找到双亲结点
}
// 把逆序编码顺序存入haffCode
for (int j = cd.length - 1; j >= 0; j--){
haffCode[i].bit[cd.length-1 - j] = cd.bit[j];
}
// 保存haffTree的信息到haffCode
haffCode[i].length = cd.length; // 保存好haffCode的长度
haffCode[i].weight = cd.weight; // 保存编码对应的权值
}
}
2.4 测试
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 哈夫曼编码!\n");
int i, j, n = 4, m = 0;
// 权值
int weight[] = {2,4,5,7};
// 初始化哈夫曼树, 哈夫曼编码
HaffNode *myHaffTree = malloc(sizeof(HaffNode) * (2*n-1));
Code *myHaffCode = malloc(sizeof(Code) * n);
// 当前n > MaxN,表示超界. 无法处理.
if (n > MaxN) {
printf("定义的n越界，修改MaxN!");
exit(0);
}
// 1.构建哈夫曼树
Haffman(weight, n, myHaffTree);
// 2.根据哈夫曼树得到哈夫曼编码
HaffmanCode(myHaffTree, n, myHaffCode);
// 3.遍历输出
for (i = 0; i < n; i++) {
printf("Weight = %d\n",myHaffCode[i].weight);
for (j = 0; j < myHaffCode[i].length; j++) // 打印编码
printf("%d", myHaffCode[i].bit[j]);
m = m + myHaffCode[i].weight * myHaffCode[i].length; // 累计WPL
printf("\n");
}
printf("Huffman's WPL is:%d\n",m);
return 0;
}
// 输出
Hello, 哈夫曼编码!
Weight = 2
110
Weight = 4
111
Weight = 5
10
Weight = 7
0
Huffman's WPL is:35
网友评论