哈夫曼，哈夫曼树的特征是什么

本文目录一览

1，哈夫曼树的特征是什么
2，Huffman是什么来的
3，哈夫曼树是二叉树吗
4，哈夫曼树的构建过程
5，赫夫曼树是否唯一
6，哈夫曼编码原理

1，哈夫曼树的特征是什么

哈夫曼树的特征：它是带权路径长度WPL最小的二叉树！

哈弗曼树一定要是权值小的在左边权值大的在右边。

哈夫曼树的特征是什么

2，Huffman是什么来的

人名：哈夫曼

我记得在《数据结构》里看到过，huffman编码。是利用人名huffman叫的。

哈夫曼在百度查它是人名也是一种事物和一种理论方法请采纳谢谢祝：家庭健康包括你

Huffman是什么来的

3，哈夫曼树是二叉树吗

哈夫曼树不一定是二叉树，也有可能有度为m的哈弗曼树，度为m的哈弗曼树只有度为m的结点和度为0的结点。

符合二叉树定义，所以是问这个问题肯定是在《数据结构》的范围内……此时哈夫曼树就是指最优二叉树。参见严版教材关于最优二叉树或哈夫曼树的定义。

问题1：这个题只能描述，而不能画出。若非空树它有三种情况：只有根结点；只有左子树；只有右子树。问题2：哈夫曼树，n个叶子结点有2n-1个结点也比较好理解，因为它只有度为0或度为2的结点，而叶子结点就是度为0结点，即为n；在二叉树中度为0的结点是度为2的结点数目加1（这点是可以证明的），所以度为2的结点数目为n-1，两者加起来就是2n-1啦。

哈夫曼树来源于哈夫曼编码，哈夫曼编码其实不只是针对二进制，可以说任何进制都能使用哈夫曼编码（详见信息与编码相关书籍）。但是在计算机领域由于使用二进制，在数据结构上只介绍了二进制的哈夫曼编码，构造出来的哈夫曼树是度为二的树。楼上，请问二叉树定义是什么？你的哈夫曼树分左右子树？

哈夫曼树是二叉树吗

4，哈夫曼树的构建过程

哈夫曼树:给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。哈夫曼树的构造：假设给定的权值如下：3,5,7,8,10,15；首先取集合中最小的两个数：3+5=8，再删除集合中3和5的值，把8放入原集合,原集合变成:7,8,8,10,15； 8 / \ 3 5再从7,8,8,10,15中再取2个最小的数构成一个树 15 / \ 8 7 / \ 3 5再从8,10,15,15中再取2个最小的数构成一个树: 18 / \ 8 10再从15,15,18中取两个最小数:15,15,构成树: 30 / \ 15 15 / \ 8 7 / \ 3 5最后把18,30构成树(此时集合中已经没元素了，就形成了哈夫曼树): 48 / \ 30 18 / \ / \ 15 15 8 10 / \ 8 7 / \ 3 5希望你能看懂！！

5，赫夫曼树是否唯一

不唯一，第一：存在左右问题。比如（1,2,4,8）选则最小的两个权值1和2之后，建立了以1+2=3的新节点，下一个结点肯定是选择4和3，那么4和3就存在谁是7的左子树，谁是右子数问题。第二：比如（1,2，3@,3￥），（注意：我这里面写得@，￥，是为了区别不同的3，并不参与运算）第一步：选择1和2，然后组成3*。第二步，应该在（3*，3@，3￥）中选择两个3，那么选择3*和3@，和选择3@和3￥是不一样的。自己画画

哈夫曼树不唯一，数据结构里不是专门有讲得么。

哦，上面的是我回答的，刚才忘了登陆了，本以为已经登陆了，结果点了一下不登陆回答就提交了。还望你采纳这个。O(∩_∩)O~

不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。历史：1951年，哈夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。

6，哈夫曼编码原理

原发布者:a2420092945Huffman树及其应用一、最优二叉树（霍夫曼树）预备知识：若干术语路d径：由一结点到另一结点间的分支所构成a→e的路径长度＝2beacfg路径长度：路径上的分支数目树长度＝10树的路径长度：从树根到每一结点的路径长度之和。带权路径长度：结点到根的路径长度与结点上权的乘积树中所有叶子结点的带权路径长度之和树的带权路径长度：霍夫曼树：带权路径长度最小的树。1Huffman树简介：WeightedPathLength树的带权路径长度如何计算？WPL=哈夫曼树则是：WPL最小的树。wklkk=1n经典之例：4d2c7a(b)5bHuffman树7a7a52bc4d5b2c(c)4d(a)WPL=36WPL=46WPL=352构造霍夫曼树的基本思想：权值大的结点用短路径，权值小的结点用长路径。构造Huffman树的步骤（即Huffman算法）：(1)由给定的n个权值{w0,w1,w2,…,wn-1，构造具有n棵扩充二叉树的森林F={T0,T1,T2,…,Tn-1，其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。(2)重复以下步骤,直到F中仅剩下一棵树为止：①在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。先举例！3例1：设有4个字符d,i,a,n，出现的频度分别为7,5,

赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。扩展资料赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。例如a7从左至右，由U至U″″，其码字为1000；a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…用赫夫曼编码所得的平均比特率为：Σ码长×出现概率上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit可以算出本例的信源熵为2.61bit，二者已经是很接近了。参考资料来源：搜狗百科-哈夫曼编码

霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下：（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。以下这个简单例子说明了这一过程。1)．字母A,B,C,D,E已被编码，相应的出现概率如下： p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.112)．C和E概率最小，被排在第一棵二叉树中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的哈夫曼编码可能由相同的数据产生。3)．各节点相应的概率如下： p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13 D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。4)．剩下节点的概率如下：p(AD)=0.29, p(B)=0.51, p(CE)=0.20AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。5)．剩下两个节点相应的概率如下：p(ADCE)=0.49, p(B)=0.51它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。6)．图03-02-2为霍夫曼编码。编码结果被存放在一个表中： w(A)=001, w(B)=1, w(C)=011, w(D)=000, w(E)=010图03-02-2 霍夫曼编码例霍夫曼编码器的编码过程可用例子演示和解释。下面是另一个霍夫曼编码例子。假定要编码的文本是： "EXAMPLE OF HUFFMAN CODE"首先，计算文本中符号出现的概率（表03-02-2）。表03-02-2 符号在文本中出现的概率符号概率E 2/25X 1/25A 2/25M 2/25P 1/25L 1/25O 2/25F 2/25H 1/25U 1/25C 1/25D 1/25I 1/25N 2/25G 1/25空格 3/25最后得到图03-02-3所示的编码树。图03-02-3 霍夫曼编码树在霍夫曼编码理论的基础上发展了一些改进的编码算法。其中一种称为自适应霍夫曼编码（Adaptive Huffman code）。这种方案能够根据符号概率的变化动态地改变码词，产生的代码比原始霍夫曼编码更有效。另一种称为扩展的霍夫曼编码（Extended Huffman code）允许编码符号组而不是单个符号。同香农-范诺编码一样，霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。这是因为这两种方法都自含同步码，在编码之后的码串中都不需要另外添加标记符号，即在译码时分割符号的特殊代码。当然，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，那怕仅仅是1位出现错误，也会引起一连串的错误，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。