数据结构----哈夫曼树
这里写目录标题
- 基本概念
- 引子
- 基本概念
- 各种路径长度
- 各种带权路径长度
- 结点的带权路径长度
- 树的带权路径长度
- 哈夫曼树
- 哈夫曼树的构造
- 理论基础
- 构造思想
- 总结
- 哈夫曼树的实现
- 哈夫曼编码
- 前缀编码
- 哈夫曼编码的思想
- 案例
- 代码实现
- 编码与解码
基本概念
引子
哈夫曼树就是寻找构造最优二叉树，用于提高效率
基本概念
各种路径长度
各种带权路径长度
结点的带权路径长度
树的带权路径长度
哈夫曼树
带权路径长度最短的树或者二叉树
也就是树的叶子结点带权路径长度之和 ：也就是叶子结点的结点路径长度（根结点到叶子结点的路径数） *权重 再求和
总结：位高权重
并且哈夫曼树不唯一
哈夫曼树的构造
理论基础
构造思想
可以看到 先将所有结点看成根结点构造出森林 并将权重赋值给结点
之后 选择两个小权重的结点 二者构造出新树 如上图 新树根结点权重为子树结点权重之和
这时要先将森林中的两个树删除 之后 将两个树构造成的新树加入森林（为了进行下一次权重的比较 从而下一步构造的顺利进行）
重复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就向右走 直到走到叶子结点 记录一个字符 重复此操作即可