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