本文目录一览

1，霍夫曼树一定是满二叉树吗

不是。满二叉树是所有分支都有左孩子右孩子结点，叶子结点在二叉树最下一层。霍夫曼树是带权路径最短，也叫最优二叉树。

霍夫曼树一定是满二叉树吗

2，什么是哈夫曼树呢

夫曼树是带权路径长度最小的二叉树，用途是平均查找信息的代价最小。 普通二叉树的用途也普通，比较通用，就是信息存储和查找。 普通二叉树可能有的只有一个子节点，而哈夫曼树一定有两个。

什么是哈夫曼树呢

3，哈夫曼树的相关知识

哈夫曼树是一种带权路径长度最短的树。...在哈夫曼树中向左分支走就是O，向右分支走就是1。 这样所有的哈夫曼树中的叶子结点就对应一系列01的组合。...这样通过哈夫曼树的思想我们就得到了BD...

哈夫曼树的相关知识

4，哈夫曼树是二叉树吗

哈夫曼树不一定是二叉树，也有可能有度为m的哈弗曼树，度为m的哈弗曼树只有度为m的结点和度为0的结点。
符合二叉树定义，所以是 问这个问题肯定是在《数据结构》的范围内……此时哈夫曼树就是指最优二叉树。参见严版教材关于最优二叉树或哈夫曼树的定义。
问题1：这个题只能描述，而不能画出。若非空树它有三种情况：只有根结点；只有左子树；只有右子树。问题2：哈夫曼树，n个叶子结点有2n-1个结点也比较好理解，因为它只有度为0或度为2的结点，而叶子结点就是度为0结点，即为n；在二叉树中度为0的结点是度为2的结点数目加1（这点是可以证明的），所以度为2的结点数目为n-1，两者加起来就是2n-1啦。
哈夫曼树来源于哈夫曼编码，哈夫曼编码其实不只是针对二进制，可以说任何进制都能使用哈夫曼编码（详见信息与编码相关书籍）。但是在计算机领域由于使用二进制，在数据结构上只介绍了二进制的哈夫曼编码，构造出来的哈夫曼树是度为二的树。楼上，请问二叉树定义是什么？你的哈夫曼树分左右子树？

5，什么是赫夫曼树

1、是一种利用二叉树实现的编码原理 霍夫曼（Huffman）编码原理 霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。 霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。 步骤进行： l）将信号源的符号按照出现概率递减的顺序排列。 2）将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。 3）重复进行步骤1和2直到概率相加的结果等于1为止。 4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。 5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。 例： 设信号源为 s＝｛s1, s2, s3, s4, s5｝ 对应的概率为p＝｛0.25，0.22，0.20, 0.18，0.15｝。 根据字符出现的概率来构造平均长度最短的异字头码字。 霍未曼编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。 霍夫曼编码具有一些明显的特点： 1) 编出来的码都是异字头码，保证了码的唯一可译性。 2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。 3) 编码长度不统一，硬件实现有难度。 4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。 5) 由于"0"与"1"的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能 2、都差不多，个人感觉c++更好学

6，到底什么是哈夫曼树啊求例子

哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。例子：1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；3、从森林中删除选取的两棵树，并将新树加入森林；4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。扩展资料：按照哈夫曼编码构思程序流程：1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。3、以本题为例，备选数组中现有元素为4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。参考资料来源:搜狗百科——哈夫曼树
我们先看一个应用例子：假如你跟别人聊天，输入了“AFTER DATA EAR ARE ART AREA”，要发给对方，在电脑的世界里，最终都是要将相关的字符转换为0 1来表示的二进制来传输，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为为了获得传送报文的最短长度，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下。于是我们构造这颗二叉树的时候，应该先选择最小权值的点来构造树，新树的权值为左右子树的权值之和，然后新的权值放回到原来的权值序列中，再次选择两个权值最小的点来构造树，如此循环最后只剩下一棵树为止。我们以字符集为“A，E，R，T，F，D”，各字母出现的次数为首先选取两个最小权值的点构造树，新的权值放回到序列中，变为 / \1 1再次选择两个权值最小的点构造树，序列变为如下： / \ 2 3 / \ 1 1按照上面的规则直到只有一颗树为止 / \ / \ 2 3 4 5 / \1 1------------------------ / \ / \ 4 5 5 8 / \ 2 3 / \ 1 1------------------------ 22 / \ 9 13 / \ / \E4 R5 5 A8 / \ 2 T3 / \ F1 D1上面的的树便是哈夫曼树了（给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树）这颗树每一个“/” 默认为0， “\”为1，就可以得到叶子结点的编码：如上面F：1000 D：1001 A：11
这么明确的算法，肯定唯一，数如下： 1.00 / \ /0 \1 0.44 0.56 / \ / \ /0 \1 /0 \1 0.21 0.23 0.27 0.29 / \ /0 \1 0.13 0.16 / \ /0 \1 0.07 0.09编码：0.07:11100.09:11110.13:1100.21:000.23:010.27:10没有谁是谁的前缀，ok. 针对补充问题：不行，生成哈夫曼树时总是取最小的两个权值作为叶子。。 针对补充问题002：上面那棵树，从下往上看，所有权值中最小的两个是0.07跟0.09，相加等0.16；原来的权值表成了：0.13，0.16(代替了0.07跟0.09),0.21，0.23，0.27；现在最小的两个是0.13，0.16，相加得到0.29；之前的权值表又成了：0.21，0.23，0.27，0.29(代替了0.13跟0.16)；现在最小的两个是0.21，0.23，相加得到0.44；之前的权值表又成了:0.27，0.29，0.44；接下来是一样的。
一、哈夫曼树的介绍Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。 这个定义里面涉及到了几个陌生的概念，下面就是一颗哈夫曼树，我们来看图解答。(1) 路径和路径长度定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 例子：100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3。(2) 结点的权及带权路径长度定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 例子：节点20的路径长度是3，它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60。(3) 树的带权路径长度定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。 例子：示例中，树的WPL= 1*100 + 2*50 + 3*20 + 3*10 = 100 + 100 + 60 + 30 = 290。比较下面两棵树上面的两棵树都是以左边的树WPL=2*10 + 2*20 + 2*50 + 2*100 = 360 右边的树WPL=290左边的树WPL > 右边的树的WPL。你也可以计算除上面两种示例之外的情况，但实际上右边的树就是二、哈夫曼树的图文解析假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为：1. 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； 2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； 3. 从森林中删除选取的两棵树，并将新树加入森林； 4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。以第1步：创建森林，森林包括5棵树，这5棵树的权值分别是5,6,7,8,15。 第2步：在森林中，选择根节点权值最小的两棵树(5和6)来进行合并，将它们作为一颗新树的左右孩子(谁左谁右无关紧要，这里，我们选择较小的作为左孩子)，并且新树的权值是左右孩子的权值之和。即，新树的权值是11。 然后，将"树5"和"树6"从森林中删除，并将新的树(树11)添加到森林中。 第3步：在森林中，选择根节点权值最小的两棵树(7和8)来进行合并。得到的新树的权值是15。 然后，将"树7"和"树8"从森林中删除，并将新的树(树15)添加到森林中。 第4步：在森林中，选择根节点权值最小的两棵树(11和15)来进行合并。得到的新树的权值是26。 然后，将"树11"和"树15"从森林中删除，并将新的树(树26)添加到森林中。 第5步：在森林中，选择根节点权值最小的两棵树(15和26)来进行合并。得到的新树的权值是41。 然后，将"树15"和"树26"从森林中删除，并将新的树(树41)添加到森林中。 此时，森林中只有一棵树(树41)。这棵树就是我们需要的哈夫曼树！三、哈夫曼树的基本操作哈夫曼树的重点是如何构造哈夫曼树。本文构造哈夫曼时，用到了以前介绍过的"(二叉堆)最小堆"。下面对哈夫曼树进行讲解。1. 基本定义[html]view plaincopyprintHuffmanNode是哈夫曼树的节点类。[html]view plaincopyprintHuffman是哈夫曼树对应的类，它包含了哈夫曼树的根节点和哈夫曼树的相关操作。2. 构造哈夫曼树[html]view plaincopyprint首先创建最小堆，然后进入for循环。每次循环时：(1) 首先，将最小堆中的最小节点拷贝一份并赋值给left，然后重塑最小堆(将最小节点和后面的节点交换位置，接着将"交换位置后的最小节点"之前的全部元素重新构造成最小堆)； (2) 接着，再将最小堆中的最小节点拷贝一份并将其赋值right，然后再次重塑最小堆； (3) 然后，新建节点parent，并将它作为left和right的父节点； (4) 接着，将parent的数据复制给最小堆中的指定节点。四、哈夫曼树的完整源码1. 哈夫曼树的节点类(HuffmanNode.java)[html]view plaincopyprint2. 哈夫曼树的实现文件(Huffman.java)[html]view plaincopyprint3. 哈夫曼树对应的最小堆(MinHeap.java)[html]view plaincopyprint4. 哈夫曼树的测试程序(HuffmanTest.java)[html]view plaincopyprint五个字符：a,b,c,d,e,它们出现的的频率为8，14，10，4，18构造相应的哈夫曼树，求出每个字符的哈夫曼编码：哈夫曼树：54/ \22 32/ \ / \c10 12 b14 e18/ \d4 a8哈夫曼编码：a:011 b:10 c:00 d:010 e:11今天做题的时候，遇到了一个关于哈夫曼树的题，由于一直不是很明白哈夫曼树的构造过程，所以找了很多资料都不是特别清楚的，直到我遇到了这篇文章，哈哈，在此分享给大家哦！注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。（1）8个结点的权值大小如下：（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。 （BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。 （BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。 好了，此时哈夫曼树已经构建好了。这是原作者的链接哦，我觉得还不错呢，大家可以去看看的！注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。（1）8个结点的权值大小如下：（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。 （BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。 （BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。 好了，此时哈夫曼树已经构建好了。

文章TAG：霍夫曼树  夫曼  一定  满二叉树  霍夫曼树  
下一篇