构造哈夫曼树和生成哈夫曼编码
一、什么是哈夫曼树？
哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。用一幅图来说明：
文章图片
它们的带权路径长度分别为：
图a： WPL=5*2+7*2+2*2+13*2=54
图b： WPL=5*3+2*3+7*2+13*1=48
可见，图b的带权路径长度较小，可以证明图b就是哈夫曼树(也称为最优二叉树)。
二、如何构建哈夫曼树
一般按下面步骤构建：
1，将所有左，右子树都为空的作为根节点。
2，在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值。
3，从森林中删除这两棵树，同时把新树加入到森林中。
4，重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。
下面是构建哈夫曼树的图解过程：
文章图片
三、哈夫曼编码
利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示"0"码，指向右子树的分支表示"1"码，取每条路径上的"0"或"1"的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码。
上图例子来说：
A，B，C，D对应的哈夫曼编码分别为：111，10，110，0
用图说明如下：
文章图片
记住，设计电文总长最短的二进制前缀编码，就是以n个字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求得的编码就是哈夫曼编码。
四、算法实现
/**
*实验题目:
*构造哈夫曼树和生成哈夫曼编码
*实验目的:
*领会哈夫曼的构造过程以及哈夫曼编码的生成过程
*实验内容:
*设计程序，构造一颗哈夫曼树，输出对应的哈夫曼
*编码和平均查找长度。并用如下数据进行验证：
*单词以及出现的频度
*TheofatoandinthatheisatonforHisarebe
*1192 677 541 518 462450 242195 190 181 174157138124123
*备注:二叉树中叶子结点个数为n,则二叉树中结点总数为(2 * n - 1)
*/
#include
#include
#define N(50)// 树中叶子结点数最大值
#define M(2 * N - 1) // 树中结点总数最大值
typedef struct
{
char data[5];
// 结点值
int weight;
// 权重
int parent;
// 双亲结点
int lchild;
// 左孩子结点
int rchild;
// 右孩子结点
}HTNode;
// 声明哈夫曼树结点类型
typedef struct
{
char cd[N];
// 存放哈夫曼编码
int start;
}HCode;
// 声明哈夫曼编码类型
/*-------------由含有n个叶子结点的ht构造完整的哈夫曼树-----------------*/
static void create_huffman_tree(HTNode ht[], int n)
{
int i;
int k;
int lnode;
int rnode;
int min1;
int min2;
// 所有结点的相关域设置初值为-1
for(i = 0;
i < 2 * n - 1;
i++)
ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
for(i = n;
i < 2 * n - 1;
i++) // 构造哈夫曼树的分支结点
{
min1 = min2 = 32767;
lnode = rnode = -1;
for(k = 0;
k <= i - 1;
k++) // 查找最小和次小的结点
{
if(ht[k].parent == -1) // 只在尚未构造二叉树的结点中查找
{
if(ht[k].weight < min1)
{
min2 = min1;
rnode = lnode;
min1 = ht[k].weight;
lnode = k;
}
else if(ht[k].weight < min2)
{
min2 = ht[k].weight;
rnode = k;
}
}
}
ht[lnode].parent = i;
// 合并两个最小和次小的结点
ht[rnode].parent = i;
ht[i].weight = ht[lnode].weight + ht[rnode].weight;
// 计算双亲结点的权重
ht[i].lchild = lnode;
// 设置双亲结点的左孩子
ht[i].rchild = rnode;
// 设置双亲结点的右孩子
}
}
/*-------------由哈夫曼树ht构造哈夫曼编码hcd-----------------*/
static void create_huffman_code(HTNode ht[], HCode hcd[], int n)
{
int i;
int f;
int c;
HCode hc;
for(i = 0;
i < n;
i++) // 根据哈夫曼树构造所有叶子结点的哈夫曼编码
{
hc.start = n;
c = i;
f = ht[i].parent;
while(f != -1) // 循环直到树根结点
{
if(ht[f].lchild == c) // 处理左孩子结点
hc.cd[hc.start--] = '0';
else // 处理右孩子结点
hc.cd[hc.start--] = '1';
c = f;
f = ht[f].parent;
}
hc.start++;
// start指向哈夫曼编码最开始字符
hcd[i] = hc;
}
}
/*-------------输出哈夫曼编码-----------------*/
static void display_huffman_code(HTNode ht[], HCode hcd[], int n)
{
int i;
int k;
int sum = 0;
int m = 0;
int j;
printf("输出哈夫曼编码:\n");
for(i = 0;
i < n;
i++)
{
j = 0;
printf("%s:\t", ht[i].data);
for(k = hcd[i].start;
k <= n;
k++)
{
printf("%c", hcd[i].cd[k]);
j++;
}
m += ht[i].weight;
sum += ht[i].weight * j;
printf("\n");
}
printf("\n平均长度 = %g\n", 1.0 * sum / m);
}
int main(void)
{
int n = 15;
int i;
HTNode ht[M];
HCode hcd[N];
char *str[] = {"The", "of", "a", "to", "and", "in", "that", "he", "is", "at", "on", "for", "His", "are", "be"};
int fnum[] = {1192, 677, 541, 518, 462, 450, 242, 195, 190, 181, 174, 157, 138, 124, 123};
for(i = 0;
i < n;
i++)
{
strcpy(ht[i].data, str[i]);
ht[i].weight = fnum[i];
}
create_huffman_tree(ht, n);
// 创建哈夫曼树
create_huffman_code(ht, hcd, n);
// 构造哈夫曼编码
display_huffman_code(ht, hcd, n);
// 输出哈夫曼编码
return 0;
}
测试结果：
输出哈夫曼编码:
The:01
of:101
a:001
to:000
and:1110
in:1101
that:11110
he:11001
is:11000
at:10011
on:10010
for:10001
His:10000
are:111111
be:111110
【构造哈夫曼树和生成哈夫曼编码】平均长度 = 3.56208
推荐阅读
- 哈夫曼树，哈夫曼编码
- c语言|哈夫曼树和哈夫曼编码
- 数据结构和算法|哈夫曼树及其编码
- 存储|哈夫曼树（Huffman tree）及哈夫曼编码
- B|B 树的简单认识
- 探索 AVL 树基础原理
- 一文搞懂决策树！ #51CTO博主之星评选#
- 二叉树面试题（前中序求后序中后序求前序）
- 红黑树
- POSTGRESQL如何存储树形数据 处理树形数据