最优⼆叉树（哈夫曼树）的构建及编码
参考：
数据结构教程（第五版）李春葆主编
⼀，概述
1，概念
结点的带权路径长度：
从根节点到该结点之间的路径长度与该结点上权的乘积。
树的带权路径长度：
树中所有叶结点的带权路径长度之和。
2，哈夫曼树（Huffman Tree）
给定 n 个权值作为 n 个叶⼦结点，构造⼀棵⼆叉树，若该树的带权路径长度达到最⼩，则称这样的⼆叉树为最优⼆叉树，也称为哈夫曼树。
哈夫曼树是带权路径长度最短的树，权值较⼤的结点离根较近。
⼆，哈夫曼树的构建
1，思考
要实现哈夫曼树⾸先有个问题摆在眼前，那就是哈夫曼树⽤什么数据结构表⽰？
⾸先，我们想到的肯定数组了，因为数组是最简单和⽅便的。⽤数组表⽰⼆叉树有两种⽅法：
第⼀种适⽤于所有的树。
即利⽤树的每个结点最多只有⼀个⽗节点这种特性，⽤ p[ i ] 表⽰ i 结点的根节点，进⽽表⽰树的⽅法。
但这种⽅法是有缺陷的，权重的值需要另设⼀个数组表⽰；每次⼦节点都要遍历⼀遍数组，⼗分浪费时间。
第⼆种只适⽤于⼆叉树。
即利⽤⼆叉树每个结点最多只有两个⼦节点的特点。从下标 0 开始表⽰根节点，编号为 i 结点即为 2
* i + 1 和 2 * i + 2，⽗节点为 ( i - 1) / 2，没有⽤到的空间⽤ -1 表⽰。
但这种⽅法也有问题，即哈夫曼树是从叶结点⾃下往上构建的，⼀开始树叶的位置会因为⽆法确定⾃⾝的深度⽽⽆法确定，从⽽⽆法构造。
既然如此，只能⽤⽐较⿇烦的结构体数组表⽰⼆叉树了。
typedef struct HTNode // 哈夫曼树结点
{
double w; // 权重
int p, lc, rc;
}htn;
2，算法思想
感觉⽐较偏向于贪⼼，权重最⼩的叶⼦节点要离根节点越远，⼜因为我们是从叶⼦结点开始构造最优树的，所以肯定是从最远的结点开始构造，即权重最⼩的结点开始构造。
哈夫曼编码树的带权路径长度
所以先选择权重最⼩的两个结点，构造⼀棵⼩⼆叉树。
然后那两个最⼩权值的结点因为已经构造完了，不会在⽤了，就不去考虑它了，将新⽣成的根节点作为新的叶⼦节加⼊剩下的叶⼦节点，⼜因为该根节点要能代表整个以它为根节点的⼆叉树的权重，所以其权值要为其所有⼦节点的权重之和。
如此，继续选取权重最⼩的两个结点，循环上⼀步骤。
这种，就是贪⼼的思想：
先是求整个最优树的问题，此时我们到两个权重最⼩的叶⼦结点，构造⼀棵⼩⼆叉树。此时为当前最优的情况。
然后将分解成了 —— 求去除了两个权值最⼩的叶⼦节点的最优树的问题。该问题与原问题在本质上是⼀样的，所以继续到两个权重最⼩的叶⼦结点，构造⼀棵⼩⼆叉树。此时仍然为当前最优的情况。
如此往复，不断贪⼼，最后将所有结点整合在⼀起就是原问题的最优解了。
3，算法步骤
① 构造森林全是根
这⼀步就是把这 n 个叶⼦节点放⼊结构体数组中：
有 n 个结点的⼆叉树的结点个数为 2n-1，所以要⽤到的数组长度为 2n-1
② 选择两⼩造新树
选择两⼩：在剩下没⽤过的叶⼦结点中到最⼩的两个数，这些结点包括树叶也包括你上⼀波造的新树的根。
③ 删除两⼩添新⼈
删除两⼩：给到的结点认好⽗亲，下次搜索时排除掉有⽗节点的结点。
添新⼈：将选择的两个权值最⼩的结点与其⽗节点构建好关系。
④ 重复 ②，③操作
结构体数组的前 n 个元素放叶⼦节点，把新⽣成的按顺序放在叶结点后⾯。
于是，我们从下标为 n 开始循环，这样要的结点全部都包含在循环变量 i 的前⾯，当然其中也包含了已经不需要考虑的结点。
三，哈夫曼树编码
1，概念
哈夫曼编码的实质：使⽤频率越⾼的字符采⽤越短的编码。
2，算法思想
如果我们只使⽤包含 0 和 1 字符串来编码的话，那么我们就可以使⽤哈夫曼树来解决哈夫曼编码的问题。
哈夫曼编码要求频率越⾼的字符采⽤越短的编码，⽽哈夫曼树是权重越⼤的叶⼦节点离根节点越远。
那么，如果我们⽤叶结点到根节点的路径来代表编码长度的话，不就符合哈夫曼编码的频率越⾼编码越短的要求吗？
⼜因为哈夫曼树是⼆叉树，⼀个⽗节点只有两个⼦节点，所以每个编码的字符只能有两种区别，正好对应 0 和 1，
我们可以⽤左节点代表 0，右节点代表 1。这样，我们⾛⼀遍叶结点到根节点的路径，该字符的编码就出来了。
当然，从根节点到叶结点也可以，不过要统⼀使⽤，不能⼀个字符是从叶结点出发，另外⼀个是从根节点出发。
3，算法步骤
① 遍历每个叶结点，给每个叶结点进⾏编码。
② 编码过程
Ⅰ⾸先是可以确定树⾼最⾼为为 n-1，因为这是⼀棵有 n 个叶⼦节点的⼆叉树，所以这样就可以⽤ n 给数组赋长了。
Ⅱ我们这⾥的编码顺序是从根节点到叶结点，但实际的遍历顺序是从叶结点到根节点（因为这样可以根据是否），所以存编码的数组就要从后往前赋值。
即使⽤下标为 0 的位置，将 n-1 位赋值为 '\0' ，然后从下标为 n -2 的位置往前遍历。
Ⅲ 然后从树叶回溯到根，每⼀个结点判断⼀下是左节点还是右节点，就知道要当前编码位是 0 还是 1 了。
4，哈夫曼编码的性质
在⼀组字符的哈夫曼编码中，任⼀字符的哈夫曼编码不可能是另⼀字符哈夫曼编码的前缀。
定性证明：
观察哈夫曼树，根节点到不同叶结点的路径必不同。
所以⼀个叶⼦节点不可能是另⼀叶⼦节点路径的某⼀部分，所以也不可能⼀个字符是另⼀字符哈夫曼编码的前缀。
四，完整代码：
#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<string.h>
#define N 666
#define inf 0x3f3f3f3f
typedef struct HTNode // 哈夫曼树结点
{
double w; // 权重
int p, lc, rc;
}htn;
htn ht[N]; // 哈夫曼树
char hcd[N][20]; // 存哈夫曼编码
void select(int i, int &c1, int &c2) // 在 ht[0 ~ i-1] 中权值最⼩的两个结点
{
double min1 = inf, min2 = inf;
for (int j = 0; j < i; j++)
{
if (ht[j].p != -1) // 在没有⽗节点的节点中查，包括未参与的和新⽣成的结点
continue;
if (ht[j].w < min1) // 到当前最⼩值
{
min2 = min1; // 原先最⼩值变成第⼆⼩
c2 = c1;
min1 = ht[j].w; // 新到的变成最⼩值
c1 = j;
}
else if (ht[j].w < min2)// 到当前第⼆⼩值
{
min2 = ht[j].w;
c2 = j;
}
}
}
void CreateHT(int n) // 创建 Huffman tree
{
// ①构造森林全是根，即所有结点的初始值置为 -1
for (int i = 0; i < 2 * n - 1; i++) //
ht[i].p = ht[i].lc = ht[i].rc = -1;
// ④重复②，③操作
for (int i = n; i < 2 * n - 1; i++)
{
// ②选择两⼩造新树，其中 c1 权值最⼩，c2 第⼆⼩
int c1 = -1, c2 = -1;
select(i, c1, c2);
// ③删除两⼩添新⼈
ht[c1].p = ht[c2].p = i;
ht[i].lc = c1, ht[i].rc = c2;
ht[i].w = ht[c1].w + ht[c2].w;
}
// 输出 Huffman tree
printf("\n该哈夫曼树为：\n");
for (int i = 0; i < 2 * n - 1; i++)
printf("结点 %2d：权值为 %.2lf，⽗节点：%2d，⼦节点：%2d，%2d\n", i, ht[i].w, ht[i].p, ht[i].lc, ht[i].rc); printf("( -1 代表不存在这个结点.)\n\n");
}
void HuffmanCoding(int n) // 哈夫曼编码
{
char code[20];
for (int i = 0; i < n; i++)
{
code[n] = 0;
int s = n - 1, c = i, p = ht[i].p; // s 指向当前编码位，c 是⼦节点，p 是⽗节点
while (p != -1) // 循环直到根结点
{
if (ht[p].lc == c)
code[s--] = '0';
else
code[s--] = '1';
c = p;
p = ht[c].p;
}
s++; // ++ 之后 s 指向当前编码的第⼀个字符
strcpy(hcd[i], code + s);
}
printf("各权值所对应的哈夫曼编码如下：\n"); // 输出哈夫曼编码
for (int i = 0; i < n; i++)
printf("权值：%.2lf，哈夫曼编码：%s\n", ht[i].w, hcd[i]);
}
{
int n; // 叶的个数
while (scanf("%d", &n) != EOF)
{
for (int i = 0; i < n; i++) // 树叶的权重
scanf("%lf", &ht[i].w);
CreateHT(n);
HuffmanCoding(n);
}
system("pause");
return0;
}
/*
输⼊数据：
8
0.05 0.29 0.07 0.08 0.14 0.23 0.03 0.11
该哈夫曼树为：
结点 0：权值为 0.05，⽗节点： 8，⼦节点：-1，-1
结点 1：权值为 0.29，⽗节点：13，⼦节点：-1，-1
结点 2：权值为 0.07，⽗节点： 9，⼦节点：-1，-1
结点 3：权值为 0.08，⽗节点： 9，⼦节点：-1，-1
结点 4：权值为 0.14，⽗节点：11，⼦节点：-1，-1
结点 5：权值为 0.23，⽗节点：12，⼦节点：-1，-1
结点 6：权值为 0.03，⽗节点： 8，⼦节点：-1，-1
结点 7：权值为 0.11，⽗节点：10，⼦节点：-1，-1
结点 8：权值为 0.08，⽗节点：10，⼦节点： 6， 0
结点 9：权值为 0.15，⽗节点：11，⼦节点： 2， 3
结点 10：权值为 0.19，⽗节点：12，⼦节点： 8， 7
结点 11：权值为 0.29，⽗节点：13，⼦节点： 4， 9
结点 12：权值为 0.42，⽗节点：14，⼦节点：10， 5
结点 13：权值为 0.58，⽗节点：14，⼦节点： 1，11
结点 14：权值为 1.00，⽗节点：-1，⼦节点：12，13
( -1 代表不存在这个结点.)
各权值所对应的哈夫曼编码如下：
权值：0.05，哈夫曼编码：0001
权值：0.29，哈夫曼编码：10
权值：0.07，哈夫曼编码：1110
权值：0.08，哈夫曼编码：1111
权值：0.14，哈夫曼编码：110
权值：0.23，哈夫曼编码：01
权值：0.03，哈夫曼编码：0000
权值：0.11，哈夫曼编码：001
*/
View Code
========== ========= ======== ======= ====== ===== ==== === == = 鹊桥仙秦观（宋）
纤云弄巧，飞信传恨，银汉迢迢暗度。⾦风⽟露⼀相逢，便胜却⼈间⽆数。
柔情似⽔，佳期如梦，忍顾鹊桥归路。两情若是长久时，⼜岂在朝朝暮暮。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论