精华内容
下载资源
问答
  • 2021-12-11 21:58:24

    哈夫曼树和编码都不唯一!只有树的WPL(带权路径长度)才是唯一的!

    更多相关内容
  • 哈夫曼树 概念 哈夫曼树也是二叉树 叶子结点的权值,权值比如重要性,某种含义的数字 叶子结点的带权路径长度 = 根到该结点的路径长度(也可以说是该叶子结点的父亲结点的高度)*该结点的权值 树的带权路径长度WPL...

    哈夫曼树

    在这里插入图片描述

    1. 概念

      • 哈夫曼树也是二叉树
      • 叶子结点的权值,权值比如重要性,某种含义的数字
      • 叶子结点的带权路径长度 = 根到该结点的路径长度(也可以说是该叶子结点的父亲结点的高度)*该结点的权值
      • 树的带权路径长度WPL = 树中所有叶子结点的带权路径长度之和
      • 哈夫曼树是WPL最小的二叉树,比它大的都不叫哈夫曼树,由此可见哈夫曼树也是最优二叉树
    2. 构造哈夫曼树

      • 每次选2个叶子结点权值最小的合并,并将2个权值的和作为新的根结点的权值
      • 由此可见,如果有n个结点,会有n-1次合并,也就是会多出n-1个非叶子结点,整个二叉树的结点=n + n -1 = 2n-1
      • 哈夫曼树不唯一,但是WPL的值都是最小值
    3. 哈弗曼编码

      • 将字符出现频次作为字符结点的权值,权值越大的叶子结点我们放在离根节点最近的地方,可以使得WPL值最小,来构造哈夫曼树,由此可见也可以压缩数据
      • 前缀编码,没有一个编码是另外一个编码的前缀,这个作用是我们可以顺序识别一串二进制代表的意思,没有歧义
      • 固定长度编码,每个字符用等长的二进制表示
      • 可变长编码,允许不同字符用不等长的二进制表示

    例子,构造哈夫曼树过程
    在这里插入图片描述

    展开全文
  • 哈夫曼树的定义 我们给树的结点赋予一个表示某种意义的值,称为该结点的权; 我们再定义从根结点到某个结点需要经过的边数,与该结点的权的乘积,称为结点的带权路径长度; 所有叶子结点的带权路径长度之和,称为树...

    哈夫曼树的定义

    我们给树的结点赋予一个表示某种意义的值,称为该结点的权

    我们再定义从根结点到某个结点需要经过的边数,与该结点的权的乘积,称为结点的带权路径长度

    所有叶子结点的带权路径长度之和,称为树的带权路径长度,记为WPL

     
    下面,先来直观感受一下WPL的含义:

    在这里插入图片描述

    (a) WPL = 7×2 + 5×2 + 2×2 + 4×2 = 36

    (b) WPL = 4×2 + 7×3 + 5×3 + 2×1 = 46

    (c) WPL = 7×1 + 5×2 + 2×3 + 4×3 = 35

     
    好了,下面给出哈夫曼树的定义:

    在含有n个带权叶子结点的所有二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树。

     
     
     

    哈夫曼树的构造

    给定n个带有权值的结点,构造哈夫曼树的算法描述如下:

    选出权值最小的两个结点,构造成一个新的结点,且新结点的权值看作两个结点的权值之和;不断重复这个过程。

    由此构造出的哈夫曼树有如下特点:

    1)每个结点最终都会称为叶子结点,权值越小的叶子越靠下,权值越大的叶子越靠上;

    2)构造过程是个两两结合的过程,因此共新建了 n-1 个结点,最终哈夫曼树的总结点数为 2n-1

    3)构造过程是个两两结合的过程,因此不会出现度为 1 的结点;

    4)构造出的哈夫曼树是不唯一的,但是最小带权路径长度(WPL)是最小且唯一的。

     
    看看图解,一下就会!!!以 {3,5,6,9,12} 为例:

    在这里插入图片描述

     
     
     

    哈夫曼编码

    在数据通信中,对字符的编码可以是长度固定的,也可以是长度不等的。可变长度编码有个极大的好处,就是可以使得字符的平均编码长度减短,起到数据压缩的效果。

    想要对不同的字符使用不同长度的编码的前提是,一个编码不能是另一个编码的前缀。这不难理解,假设合法编码有“110”、“11”、“0”,那么在翻译“1100”时,分割结果是不唯一的。

    哈夫曼树有一个优秀的性质,即权值越小的叶子越靠下,权值越大的叶子越靠上。那么,如果我们把叶子结点权值设置为字符出现的频度,比给边标记上0/1,将从根结点到叶子经过的边的所有标记序列作为编码的话——频度越高的字符编码越短,频度越低的字符编码越长,并且不会出现一个编码是另一个编码的前缀的情况!

    还是看个栗子吧 >_<!!!

    在这里插入图片描述

    展开全文
  • 哈夫曼树

    万次阅读 多人点赞 2017-08-05 23:34:19
    哈夫曼树不可能存在度为1的结点 生成哈夫曼树的第一步就是在结点集合中找到两个权值最小的结点,然后生成一棵二叉树 树中任意节点的权值一定大于自己的左右孩子,但不能保证一定不小于其他下一任结点的权值。设...

    哈夫曼树节点个数一定是奇数
    假设哈夫曼树是二叉的话,则度为0的结点个数为N,度为2的结点个数为N-1,则结点总数为2N-1。


    哈夫曼树的形态不是唯一的,但是它的带权路径长度WPL是唯一的。
    如:3,5,6
    可以构造出
    14
    8 6
    3 5

    14
    6 8
    3 5
    这两种形态,所以哈夫曼树形态不唯一


    哈夫曼树不可能存在度为1的结点
    生成哈夫曼树的第一步就是在结点集合中找到两个权值最小的结点,然后生成一棵二叉树
    树中任意节点的权值一定大于自己的左右孩子,但不能保证一定不小于其他下一任结点的权值。

    设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。

    哈夫曼树不存在入度为1 的结点,所以n0=n2+1
    设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有(2m)个空指针域; n0=m
    树的二叉链表存储结构就是孩子-兄弟表示法。
    孩子-兄弟表示法:数据域是结点,如A; 有两个指针域:1)指向长子 2)指向右兄弟
    哈夫曼树的孩子-兄弟表示法的空指针域有三种情况:(1)叶子结点长子域一定为空m个(2)根节点的右兄弟域一定为空 1个 (3)除去根节点外,哈夫曼树的其余结点个数中有一半结点的右兄弟域为空 (n总-1)/2=n2
    所以空指针域=m+1+n2=2m

    哈夫曼树权值结点的父结点实际上是没有值的


    
    一棵哈夫曼树共有215个结点,对其进行哈夫曼编码,共能得到()个不同的码字

    哈夫曼树并不是满二叉树,是正则二叉树(也叫正规二叉树),即其中只有度为0和度为2的结点
    因为n0 = n2 + 1,n = n0 + n2; 所以 n = 2n0 - 1,即n0 = (n + 1) / 2;叶子结点n0对应的即是不同的编码。
    至于满二叉树当然也是正则二叉树的特例。

    展开全文
  • 哈夫曼树的构造算法想必我们大家都是耳熟能详的,对于大多数的题目都可以轻松构造出来,但是,我们也知道哈夫曼树的构造有的简单,有的较难,存在多种情况。 我们首先看哈夫曼树的构造方法描述 (1)、根据 n 个给定...
  • 哈夫曼树以及哈夫曼编码

    千次阅读 2017-01-11 15:39:10
    1.哈夫曼树 假设有n个权值{w1, w2, …, wn},试构造一棵含有n个叶子结点的二叉树,每个叶子节点带权威wi,则其中带权路径长度WPL最小的二叉树叫做最优二叉树或者哈夫曼树。 特点:哈夫曼树中没有度为1的结点,故...
  • 哈夫曼树和哈夫曼编码

    千次阅读 2020-02-07 23:25:34
    1.哈夫曼树 叶子结点的路径长度是指从根结点出发到达该结点所经过的边数。 把叶子结点的权值乘以其路径长度的结果称为这个叶子结点的带权路径长度。 另外,树的带权路径长度( Weighted PathLength of Tree,WPL)...
  • 哈夫曼树、哈夫曼编码详解

    千次阅读 多人点赞 2021-06-17 09:33:06
    哈夫曼树、哈夫曼编码,也就这么一回事,一文搞懂!
  • 哈夫曼树(C语言实现)

    万次阅读 多人点赞 2021-06-15 17:15:11
    文章目录哈夫曼树的基本概念哈夫曼树的构建构建思路代码实现哈夫曼编码的生成编码生成思路代码实现完整代码展示以及代码测试 哈夫曼树的基本概念 在认识哈夫曼树之前,你必须知道以下几个基本术语: 1、什么是路径?...
  • 根据输入的权值建立一棵哈夫曼树,并显示该树的结点序号、双亲结点、左/右孩子结点以及各结点所对应的哈夫曼编码。
  • 哈夫曼树原理,及构造方法

    万次阅读 多人点赞 2018-08-05 12:13:21
    哈夫曼树(最优二叉树) 百度百科:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin 一. 目的: 找出存放一串字符所需的最少的二进制编码 二. 构造方法: 首先统计出每...
  • 详解哈夫曼树和哈夫曼编码

    千次阅读 多人点赞 2021-04-25 11:01:29
    哈夫曼树 并查集是一种用来管理元素分组情况的数据结构,可以高效地进行查询、合并操作,但无法进行分割操作。 1.查询元素a和元素b是否属于同一组 2.合并元素a和元素b所在的组 并查集使用树形结构实现,但不是...
  • 堆与哈夫曼树

    2021-11-29 18:52:12
    堆是一棵完全二叉树,中每一个结点的值都不小于(不大于)其左右孩子的值。 大顶堆:父亲结点的值大于等于孩子结点的值。 小顶堆:父亲结点的值小于等于孩子结点的值。 堆一般用于优先队列的实现,而优先队列一般...
  • 哈夫曼树构造以及代码实现

    千次阅读 2021-06-14 22:36:52
    哈夫曼树的构造什么是哈夫曼树理解哈夫曼树哈夫曼树的构造哈夫曼树构造-代码实现 什么是哈夫曼树 构造一颗二叉树,该树的带权路径长度达到最小,称为最优二叉树,也称为哈夫曼树(Huffman Tree) 注:带权路径长度...
  • 学习笔记:哈夫曼树及其应用

    千次阅读 2021-12-14 02:50:44
    哈夫曼树及其应用哈夫曼树及其应用哈夫曼树相关概念哈夫曼树的建立哈夫曼算法的实现哈夫曼编译码相关概念哈夫曼树设计编码哈夫曼编码的构造哈夫曼编码的译码哈夫曼编码算法(难度超级大) 哈夫曼树及其应用 哈夫曼树...
  • 哈夫曼树 哈夫曼树的定义:设二叉树具有 n 个带权值的叶节点,那么从根节点到各个叶节点的路径长度与相应叶节点权值的乘积的和,叫作二叉树的带权路径长度 WPL (Weighted Path Length)。具有最小带权路径长度的...
  • 一、哈夫曼树的概念 哈夫曼树也叫最优二叉树,在了解他的定义之前,我们先来看看以下这几个词的定义。 1、背景定义 ????路径:从树中一个节点到另一个节点间的分支构成这两个节点间的路径。 ????路径长度:路径...
  • 数据结构——哈夫曼树及其应用

    千次阅读 2022-02-02 14:49:51
    哈夫曼树及其应用哈夫曼的基本概念 哈夫曼的基本概念 路径:从树中一个结点到另一个结点之间的分支构成这两个结点间的路径 结点的路径长度:两结点间路径上的分支数 树的路径长度:从树根到每一个结点的路径长度之...
  • 本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下准备工作:1、定义一个结构体,表示一个节点。其中,这个结构体有4个成员变量,分别表示是这个节点的权值,父节点及左右子节点的下标2、...
  • 哈夫曼树及其应用

    2022-03-03 08:57:14
    哈夫曼树及其应用 判断树:用于描述分类过程的二叉树 假设 小于60分的同学有5% 60-70 15% 70-80 40% 80-90 30% >90 10% 显然:两种判别树的效率是不一样的 问题:能不能找到一种效率最高的判别树呢? 这就是...
  • 【数据结构】哈夫曼树及哈夫曼编码实现(C语言)

    千次阅读 多人点赞 2022-02-12 11:13:38
    哈夫曼树1.1 基本概念1.2 构造哈夫曼树1.3 哈夫曼树的类型定义1.4 哈夫曼树创建的算法实现2. 哈夫曼编码实现2.1 哈夫曼编码2.2 完整代码2.3 运行结果 1. 哈夫曼树 1.1 基本概念 路径:指从根结点到该结点的分支序列...
  • 哈夫曼树及python实现

    2021-01-29 16:44:38
    最近在看《tensorflow实战》中关于RNN一节,里面关于word2vec中涉及到了哈夫曼树,因此在查看了很多博客(文末)介绍后,按自己的理解对概念进行了整理(拼凑了下TXT..),最后自己用python实现Haffuman树的构建及编码。...
  • 数据结构--哈夫曼树

    千次阅读 2022-03-03 21:32:43
    哈夫曼树及其应用 1、哈夫曼树的基本概念 路径:从树中一个结点到另一个结点之间的分支构成这两个结点间的路径 结点的路径长度:两结点间路径上的分支数。 树的路径长度:从树根到每一个结点的路径...
  • 1.哈夫曼树不是唯一的: 当有a+b=c情况出现时(或者有更多个相同值的节点)就会有不一致的情况,哈夫曼树的非叶子节点的子两个节点互换任然是哈夫曼树 2.没有度为1的节点 3. n0:叶结点总数 n1:只有一个儿子的结点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,275
精华内容 1,710
关键字:

哈夫曼树唯一吗