填空 哈夫曼编码

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

哈夫曼编码

某电文由8个字母组成,字母出现的频率如下表所示,请写出字母的哈夫曼编码。

字母 频率 哈夫曼编码
A 22
B 15
C 4
D 3
E 37
F 10
G 7
H 2

因为有着八个元素,所以要预留2*n-1(n=8)即15个空位置

如下图所示求哈夫曼编码即使要把给填满

name weight parent lchild rchild
A 22 0
B 15 0
C 0
D 0
E 37 0
F 0
G 0
H 0
I
J
K
L
M
N
O

怎么求I?

首先在I的上方选取两个weight(权重)最小的点,I的值即为他们的和

由上图分析可知

I(weight)=H(weight)+D(weight)

画成图就是:

填空 哈夫曼编码
由此图可知

I的权重为5,父母为0(无父母),左子树为H,右子树为D

I 5 0 H D

H,D的父母也要修改为(I)

H 2 I
D 3 I

然后再从J的上方挑选两个子树合成新的树

选出 C和H分别作为J的左右子树,(C<H即是4<5)

即需要修改:

C 4 J 0 0
I 5 J H D
J 9 0 C I

 依次类推将所有的元素补全构建成完整的树:

即是:

填空 哈夫曼编码

求编码只求编码区 (ABCDEFGH)

E从根开始向下查找 0

A从根开始向下查找 1 0

B从根开始向下查找 1 1 0

填空 哈夫曼编码

由图可知各个字符的哈夫曼编码

 

电文总长度(WPL)为 

所有红节点的和 

即5+9+16+26+41+63+100=260

填空 哈夫曼编码

 

2 分

 位。文章来源地址https://www.toymoban.com/news/detail-475470.html

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

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

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

相关文章

  • 哈夫曼树,哈夫曼编码及解码详解

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

    2024年02月05日
    浏览(45)
  • 哈夫曼树详解及其应用(哈夫曼编码)

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

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

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

    2023年04月09日
    浏览(49)
  • 数据结构——哈夫曼树与哈夫曼编码

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

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

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

    2023年04月15日
    浏览(61)
  • 数据结构之哈夫曼树和哈夫曼编码

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

    2024年02月11日
    浏览(43)
  • 哈夫曼树及哈夫曼编码(考试常考版)

    哈夫曼树的基本概念 哈夫曼树的定义是对一组具有确定权值的叶子节点,选出最小带权路径长度的二叉树为哈夫曼树(WPL最小),也称最优二叉树 哈夫曼算法的实现 注意:哈夫曼树在构造时选择两个最小的权值点,默认小的在左边大的在右边,但实际上并没有硬性规定,可以

    2024年02月11日
    浏览(55)
  • 数据结构课程实验五:哈夫曼树与哈夫曼编码

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

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

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

    2024年02月06日
    浏览(51)
  • 经典算法: 哈夫曼编码

    从 A 结点到 B 结点所经过的分支序列叫做从 A 结点到 B 结点的 路径; 从 A 结点到 B 结点所经过的分支个数叫做从 A 结点到 B 结点的 路径长度; 从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作 该二叉树的路径长度。 设二叉树有 n 个带权值的叶结点,定义从二叉

    2024年02月06日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包