哈夫曼树及哈夫曼编码(考试常考版)

这篇具有很好参考价值的文章主要介绍了哈夫曼树及哈夫曼编码(考试常考版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

哈夫曼树的基本概念

哈夫曼树的定义是对一组具有确定权值的叶子节点,选出最小带权路径长度的二叉树为哈夫曼树(WPL最小),也称最优二叉树

哈夫曼算法的实现

注意:哈夫曼树在构造时选择两个最小的权值点,默认小的在左边大的在右边,但实际上并没有硬性规定,可以互换,对长度没有影响,但本文默认小的在左边大的在右边
1.对权值节点排序,在n个权值节点中选出两个最小的,这两个节点作为左右子树形成一棵新的二叉树,根节点的值是左右子树权值的加和
2.将原序列中最小的两个权值删除,将新的权值加入到序列中(原最小两个权值的和),并排序
3.不断重复1和2步骤,直至只剩下一棵树**(结束的表示是序列只剩1个节点值)**,此树为所构造的哈夫曼树
下面用图说明哈夫曼树的构造过程,给定权值1 5 2 6 10 7,要求构造出哈夫曼树
初始状态为
哈夫曼树及哈夫曼编码(考试常考版)

1.将权值进行排序得到1 2 5 6 7 10,选出权值最小的两个节点分别是1和2,将1和2作为左右子树生成一棵二叉树,根节点值为3
2.将最小的两个节点(1,2删除),将节点3加入到序列中,此时序列为3 5 6 7 10,即
哈夫曼树及哈夫曼编码(考试常考版)
3.由于序列中的所有节点(剩余5个)大于1个,继续循环上述1和2过程,此时序列为3 5 6 7 10,将权值最小的两个节点3和5作为左右子树生成新的一棵二叉树,根节点为3+5=8
4.将3和5节点删除,将节点8加入到序列中,重新排序,此时序列为6 7 8 10,如下图
哈夫曼树及哈夫曼编码(考试常考版)
5.由于并没有消耗完序列中的所有节点(剩余4个)大于1个,继续循环上述1和2过程,此时序列为6 7 8 10,将权值最小的两个节点6和7作为左右子树生成新的一棵二叉树,根节点为6+7=13
6.将6和7节点删除,将节点13加入到序列中,重新排序,此时序列为8 10 13,如下图
哈夫曼树及哈夫曼编码(考试常考版)
7.由于序列中的所有节点(剩余3个)大于1个,继续循环上述1和2过程,此时序列为8 10 13,将权值最小的两个节点8和10作为左右子树生成新的一棵二叉树,根节点为8+10=18
8.将6和7节点删除,将节点18加入到序列中,重新排序,此时序列为13 18,如下图
哈夫曼树及哈夫曼编码(考试常考版)
9.由于序列中的所有节点(剩余2个)大于1个,继续循环上述1和2过程,此时序列为13 18,将权值最小的两个节点13和18作为左右子树生成新的一棵二叉树,根节点为13+18=31
10.将13和18节点删除,将节点31加入到序列中,此时序列为31,如下图
哈夫曼树及哈夫曼编码(考试常考版)
11.此时序列只剩1个元素,循环结束,所生成的树即为哈夫曼树。

哈夫曼编码

在通信传送时,数据表现为0和1的二进制形式。为了提高传输的速度,通常会进行数据压缩。同时,要保证编码不存在二义性。哈夫曼编码符合上述要求,能达到较优的编码方式,其原理就是自底向上构建哈夫曼树
例:假设某报文由{‘l’,‘m’,‘y’,‘z’,‘j’,‘h’}六个字符组成,每个字符出现的频率分别是{0.24,0.16,0.2,0.08,0.02,0.3},为这6个字符设计哈夫曼编码

数据预处理

首先可以将字符出现的频率转换为整数,即每个概率乘100,得到相应权值

字符 权值
l 24
m 16
y 20
z 8
j 2
h 30
构造哈夫曼树

此时l字符对应权值为24,m字符对应权值为16.等,得到6个节点的权值后,按照上文讲到的方法构造哈夫曼树(不断循环方式1和方式2直至只剩下一棵树),具体细节不再赘述。
生成的哈夫曼树如下:
哈夫曼树及哈夫曼编码(考试常考版)

按照哈夫曼编码的规则,每个根节点的左子树编码为0 每个根节点的右子树编码为1
根据上述规则可以生成每个字符(即出现频率的节点 如l为24的节点为01)对应的编码

字符 编码
l 01
m 101
y 00
z 1001
j 1000
h 11

用哈夫曼编码得到的序列长度应为24 * 2+16 * 3 + 20 * 2 + 8 * 4 + 2 * 4 + 30 * 2 = 236
而利用等长编码由于字符数为6位,需要用3位二进制数表示,因此序列长度为300
可以看到哈夫曼编码的序列明显小于等长编码得到的序列,比例为236/300。文章来源地址https://www.toymoban.com/news/detail-510574.html

到了这里,关于哈夫曼树及哈夫曼编码(考试常考版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 哈夫曼树与哈夫曼编码

    哈夫曼树:结点中赋予一个某种意义的值,称为结点的权值,从根结点开始,到目标结点经过的边数,称为路径长度,路径长度乘以权值,称为带权路径长度; 例如:根结点代表着快递集散点,一个叶子结点权值是5,在业务逻辑中代表着重量是5斤的货物📦,路径长度是3,

    2024年02月05日
    浏览(49)
  • 哈夫曼树、哈夫曼编码和字典树

    目录 哈夫曼树 树的带权路径长度(wpl) 哈夫曼编码 代码实现哈夫曼树 封装哈夫曼树的节点 构建哈夫曼树 字典树 执行流程 代码实现字典树 封装字典树的节点 构建字典树         哈夫曼树(Huffman Tree)是一种带权路径长度最短的二叉树。哈夫曼树常常用于数据压缩,其压

    2023年04月09日
    浏览(50)
  • 哈夫曼树详解及其应用(哈夫曼编码)

    一,哈夫曼树的基本概念 路径: 从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径 结点的路径长度 :两结点之间路径上的 分支数 树的路径长度: 从 树根 到每一个结点的 路径长度之和 . 记作:TL 权(weight): 将树中结点赋给一个有着某种含义的数值

    2024年02月04日
    浏览(49)
  • 哈夫曼树,哈夫曼编码及解码详解

    🌍新人小白的博客 ⌛️希望大家多多关注 🌱一起加油,共同成长 🎃以后会经常更新哒~🙈 ⭐️个人主页: 收藏加关注,永远不迷路~⭐️ 一: 顺序表的操作,你真的学会了吗? 二: 顺序栈的基本操作 三: 循环队列的基本操作,你学会了吗? 四: 单链表的操作(超详细

    2024年02月05日
    浏览(45)
  • 数据结构——哈夫曼树与哈夫曼编码

    1.1 基本概念 路径 :指从根结点到该结点的分支序列。 路径长度 :指根结点到该结点所经过的分支数目。 结点的带权路径长度 :从树根到某一结点的路径长度与该结点的权的乘积。 树的带权路径长度(WPL) :树中从根到所有叶子结点的各个带权路径长度之和。 哈夫曼树 是由

    2024年02月05日
    浏览(46)
  • 数据结构之哈夫曼树和哈夫曼编码

    切入正题之前,我们先了解几个概念: 路径:从树的一个结点到另一个结点分支所构成的路线 路径长度:路径上的分支数目 树的路径长度:从根结点出发到每个结点的路径长度之和 带权路径长度:该结点到根结点的路径长度乘以该结点的权值 树的带权路径长度:树中所有

    2024年02月11日
    浏览(46)
  • 数据结构之哈夫曼树与哈夫曼编码

    编码是信息处理的基础(重新表示信息)。 普通的编码是等长编码,例如7位的ASCIL编码,对出现频率不同的字符都使用相同的编码长度。 但其在传输和存储等情况下编码效率不高 。 可使用不等长编码,来压缩编码:高频字符编码长度更短,低频字符编码长度更长。   [例

    2023年04月15日
    浏览(64)
  • 数据结构课程实验五:哈夫曼树与哈夫曼编码

    实验日期:2022-12-20   目录 一、实验目的 1、掌握哈夫曼树的建立 2、掌握哈夫曼编码方式 二、实验内容

    2024年02月05日
    浏览(50)
  • 【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码

    超详细讲解哈夫曼树(Huffman Tree)以及哈夫曼编码的构造原理、方法,并用代码实现。 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径。 结点的路径长度 :两结点间路径上的 分支数 。 树的路径长度: 从树根到每一个结点的路径长度之和。记作: TL  权

    2024年02月06日
    浏览(53)
  • 哈夫曼编码

    一、 哈夫曼编码介绍 1:什么样的前缀码能使得电文的总长最短? 2、哈夫曼编码案例 3、哈夫曼编码优势 4、哈夫曼编码示例

    2024年02月16日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包