数据结构【哈夫曼树】

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

哈夫曼树的概念

最优二叉树也称哈夫曼 (Huffman) 树,是指对于一组带有确定权值的叶子结点,构造的具有最小带权路径长度的二叉树。权值是指一个与特定结点相关的数值。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

涉及到的几个概念:
路径:
从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。
结点的路径长度:
两结点间路径上的分支数。
树的路径长度:
从树根到每一个结点的路径长度之和。记作: TL。
权(weight):
将树中结点赋给一个有着某种含义的数值则这个数值称为该结点的权。
结点的带权路径长度:
从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度:
树中所有叶子结点的带权路径长度之和。
二叉树的带权路径长度 (Weighted Path Length):
二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。
如果二叉树中的所有叶子结点都具有一个特定的权值,则可将这一概念加以推广。设二叉树具有n个带权值的叶子结点,那么从根结点到各个叶子结点的路径长度与该叶子结点相应的权值的乘积之和叫做又树的带权路径长度,记为:
数据结构【哈夫曼树】,数据结构与算法,数据结构,算法
其中,wk为第k个叶子结点的权值,Lk为第k个叶子结点的路径长度。
数据结构【哈夫曼树】,数据结构与算法,数据结构,算法
最优树:带权路径长度(WPL)最短的树

注:
“带权路径长度最短”是在“度相同”的树中比较而得的结果,因此有最优二叉树、最优三叉树之称等等。

最优二叉树:带权路径长度(WPL)最短的二叉树

因为构造这种树的算法是由哈夫曼教授于 1952 年提出的所以被称为哈夫曼树,相应的算法称为哈夫曼算法。

哈夫曼树的构造

哈夫曼算法(构造哈夫曼树的四句口诀)
(1)根据n个给定的权值{ w1、w2、…、wn}构成n棵二叉树的森林F=(T1、T2、…、Tn},其中Ti只有一个带权为 wi的根结点。
构造森林全是根
(2)在F中选取两棵根结点的权值最小的树作为左右子树,构造一棵新的二叉树,且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
选用两小造新树
(3)在F中删除这两棵树,同时将新得到的二又树加入森林中。
删除两小添新人
(4)重复(2)和(3),直到森林中只有一棵树为止,这棵树即为哈夫曼树。
重复 2、3 剩单根
数据结构【哈夫曼树】,数据结构与算法,数据结构,算法

可以得出:
1)哈夫曼树的节点的度为0或2,没有度为1的节点。
2)包含n个叶子节点的哈夫曼树中共有2n-1个节点。
3)包含n棵树的森林要经过n-1次合并才能形成哈夫曼树,共产生n-1个新节点。

构造算法的实现

顺序结构存储–一维结构数组

typedef struct (
	int weight;
	int parent, lch, rch;
)HTNode,*HuffmanTree;

先初始化再构造
1.初始化HT[1…2n-1]: lch=rch=parent=0;
2. 输入初始n个叶子结点: 置HT[1…n]的weight值;
数据结构【哈夫曼树】,数据结构与算法,数据结构,算法
3.进行以下n-1次合并,依次产生n-1个结点HT[i],i=n+1…2n-1:
a) 在HT[1.i-1]中选两个未被选过(从parent ==_0 的结点中选)的weight最小的两个结点HT[s1]和HT[s2],s1、s2为两个最小结点下标;
修改HT[s1]和HT[s2]的parent值: HT[s1] .parent=i; HT[s2] .parent=i;b)修改新产生的HT[i]:
HT[il.weight=HT[s1].weight + HT[s2].weight
HT[i]. lch=s1; HT[i]. rch=s2;
数据结构【哈夫曼树】,数据结构与算法,数据结构,算法

哈夫曼树应用

哈夫曼编码

数据结构【哈夫曼树】,数据结构与算法,数据结构,算法

哈夫曼编码的算法实现

数据结构【哈夫曼树】,数据结构与算法,数据结构,算法
示例:
数据结构【哈夫曼树】,数据结构与算法,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-632889.html

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

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

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

相关文章

  • 【数据结构与算法】哈夫曼编码(最优二叉树)实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(47)
  • 数据结构“基于哈夫曼树的数据压缩算法”的实验报告

    一个不知名大学生,江湖人称菜狗 original author: jacky Li Email : 3435673055@qq.com Last edited: 2022.11.20 目录 数据结构“基于哈夫曼树的数据压缩算法”的实验报告 一、实验目的 二、实验设备 三、实验内容 1.【问题描述】 2.【输入要求】 3.【输出要求】 4.【实验提示】 四、实验步骤

    2024年02月09日
    浏览(61)
  • 【数据结构与算法】哈夫曼编码(最优二叉树实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(45)
  • 数据结构与算法(C语言版)---哈夫曼编译码器

    1.1、问题阐述 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道) ,每端都需要一个完整的编/译

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

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

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

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

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

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

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

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

    2024年02月05日
    浏览(50)
  • 数据结构-哈夫曼树

    介绍 哈夫曼树,指 带权路径长度最短的二叉树 ,通常用于数据压缩中 什么是带权路径长度? 假设有一个结点,我们为它赋值,这个值我们称为权值,那么从根结点到它所在位置,所经历的路径,与这个权值的积,就是它的带权路径长度。 比如有这样一棵树,D权值为2  从

    2024年02月20日
    浏览(44)
  • 数据结构----哈夫曼树

    哈夫曼树就是寻找构造最优二叉树,用于提高效率 各种路径长度 各种带权路径长度 结点的带权路径长度 树的带权路径长度 哈夫曼树 带权路径长度最短的树或者二叉树 也就是树的叶子结点带权路径长度之和 :也就是叶子结点的结点路径长度(根结点到叶子结点的路径数)

    2024年01月21日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包