基本概念

引子

哈夫曼树就是寻找构造最优二叉树，用于提高效率

基本概念

各种路径长度

各种带权路径长度

结点的带权路径长度

树的带权路径长度

哈夫曼树

带权路径长度最短的树或者二叉树

也就是树的叶子结点带权路径长度之和 ：也就是叶子结点的结点路径长度（根结点到叶子结点的路径数） *权重 再求和


总结：位高权重
并且哈夫曼树不唯一

哈夫曼树的构造

理论基础

构造思想

可以看到 先将所有结点看成根结点构造出森林 并将权重赋值给结点
之后 选择两个小权重的结点 二者构造出新树 如上图 新树根结点权重为子树结点权重之和
这时要先将森林中的两个树删除 之后 将两个树构造成的新树加入森林（为了进行下一次权重的比较 从而下一步构造的顺利进行）
重复23步 直到剩单根

度 是指结点有的子树个数

哈夫曼树结点的度只能是0或者2
n个叶子结点的哈夫曼树 一共有2n-1个结点 分析如上橙色框

总结

哈夫曼树的实现

首先是已知叶子结点的个数以及权重

依次放入结构数组的前面 数组一共长度是2n 因为结点一共有2n-1 所以构造2n的数组 不用0下标

进行第二步 合并的时候 将新合并出来的结点往后依次放入 所以根结点是数组中的最后一个位置

新节点合成的时候 要修改新节点数组中的孩子结点下标 两个孩子要修改数组中双亲的下标

之后重复查找最小的权重的两个结点 前提是parent值是空 这是判断的关键 一旦parent值不为空的时候 就相当于退出了比较

初始化

上图中select方法 功能是在HT[K]中选择两个双亲域为0并且权重最小的结点 并返回s1 s2 用于后续操作

方法参数中i-1 是新合成结点的下标 ，在选最小的两个结点时 要从新节点前面选 这里对应理论分析中“第三步的a步骤”
i会逐渐递增

哈夫曼编码

前缀编码

图中为非前缀编码 所以要设计任意一个字符的编码都不是另一个字符编码的前缀
但是可以前缀一样 后面不一样

哈夫曼编码的思想

要想出现次数最多的编码最短 正好对应哈夫曼树的权重越大离跟结点越近的特点

所以在路径上标注0 或者 1
看从根结点到某一个叶子结点经过的路径 那些路径得出来的编码就是字符对应的二进制编码

因为叶子结点不会出现一个字符的路径完全包含另一个字符的路径 所以也就是前缀编码
并且要想出现次数最多的编码最短 正好对应哈夫曼树的权重越大离跟结点越近的特点 所以哈夫曼编码效率更高

因为叶子结点不会出现一个字符的路径完全包含另一个字符的路径 所以也就是前缀编码
并且要想出现次数最多的编码最短 正好对应哈夫曼树的权重越大离跟结点越近的特点 所以哈夫曼编码效率更高

案例

先根据哈夫曼树的设计思想 画出来哈夫曼树 在路径上标注0 1

代码实现

其中HC数组是指针数组 每个指针指向对应的字符串 也就是字符串的头指针

编码与解码

进行哈夫曼编码时 构造指针数组



先根据哈夫曼树的构造思想+字符频度表 构造出哈夫曼树 标上各个叶子结点代表的字符 之后开始解码 0就向左走 1就向右走 直到走到叶子结点 记录一个字符 重复此操作即可