哈夫曼树的构造唯一吗,同样的权 所构造出的不同的哈夫曼树 的代权路径是唯一的么？ 求15 3 14 2 6 9 16

哈夫曼树的构造唯一吗,同样的权 所构造出的不同的哈夫曼树 的代权路径是唯一的么？ 求15 3 14 2 6 9 16详细介绍

本文目录一览： 哈夫曼树是否唯一？

哈弗曼树可以不唯一，但是他们具有相同的带权路径长度，另外，哈弗曼编码才是唯一的。
哈夫曼树不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
设二叉树具有n个带权值的叶子结点，则从根结点到每一个叶子结点的路径长度与该叶子结点权值的乘积之和称为二叉树路径长度，记做：WPL=W1L1+W2L2+WnLn等等；其中：n为二叉树中叶子结点的个数；Wk为第k个叶子的权值；Lk为第k个叶子结点的路径长度。
哈夫曼树构造
结构化的Huffman算法生成的Huffman树子树都是有序的，所以一般生成Huffman树时都为节点排序，即使这样结果也不唯一。
哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。

赫夫曼树是否唯一

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

给定一组权值，可以唯一构造出一棵哈夫曼树ma？

不可以。因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
哈夫曼树（霍夫曼树）又称为最优树.
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是
带权路径长度之和最小
不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
扩展资料：
一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
一个结点的权值实际上就是这个结点子树在整个树中所占的比例.abcd四个叶子结点的权值为7，5，2，4， 这个7，5，2，4是根据实际情况得到的。
比如说从一段文本中统计出abcd四个字母出现的次数分别为7,5,2,4. 说a结点的权值为7，意思是说a结点在系统中占有7这个份量。实际上也可以化为百分比来表示，但反而麻烦,实际上是一样的。

高手指点，给定一组确定权值的节点，构造出来的哈夫曼树唯一吗？那岂不是得到的哈弗曼编码也不唯一了？

选出最小和次小之后哪个放左边都行的，哈弗曼编码唯一只是说得到的码是唯一，但是可以有许多种码，只是它能够唯一地编码和解码。
就是不唯一啊，比如说对于一个最简单的字符串进行编码：ab
那么有可能是a是0，b是1，也有可能是a是1，b是0
不过一般是按出现顺序组织树的

哈夫曼树的创建

哈夫曼树不一定是唯一的，选出最小和次小之后哪个放左边都行的，哈弗曼编码唯一只是说得到的码是唯一，但是可以有许多种码，只是它能够唯一地编码和解码。所以，上面两个图应该都是正确的。如果你习惯按照左小右大的规则来构造的话，那只能选择第二幅图了。

数据结构判断题：n个不同权值的结点，则根据这n个结点构造的哈夫曼树的结构是唯一的。

结构也不一定唯一，一旦构造过程中间出现某两个结点权值一样，并且只能选择一个时，此时形态也不唯一

什么是哈夫曼编码？

比较如下：
1、码字不同。
哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以他的优点是编码效率唯一性。而二进制编码所构造的码字是唯一。
2、长度不同
哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字，比较精准，二进制编码是用预先规定的方法将文字、数字或其他对象编成二进制的数码，或将信息、数据转换成规定的二进制电脉冲信号。二进制是最基础的编码。
3、稳定性不同
哈夫曼编码的稳定性比较差。如果改变其中一位数据就会产生改变。二进制编码具有抗干扰能力强，可靠性高等优点。
参考资料来源：百度百科-哈夫曼编码
参考资料来源：百度百科-二进制编码
哈夫曼编码是一种编码方式，它是一种线性的前缀编码方式，它利用了信源符号的统计特性，将出现概率高的符号用短码编码，出现概率低的符号用长码编码。这样可以使得编码后的平均码长最短，可以最大化压缩效果。
哈夫曼编码是1952年由David A. Huffman提出的，通常使用哈夫曼树来实现。哈夫曼树是一种带权赋值树形结构，它满足哈夫曼编码的要求，并且能够在编码过程中计算出最优编码方案。

哈夫曼树编码一定是左边为0，右边为1吗？

注：0和1表示左子树还是右子树没有明确规定。因此左右节点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但是各个哈夫曼树的带权路径长度相同且为最优。
你也可以左边为1，右边为0，只不过数建起来是反的。想怎么实现就怎么实现、能解决问题就行。

同样的权 所构造出的不同的哈夫曼树 的代权路径是唯一的么？ 求15 3 14 2 6 9 16

摘自百度百科：给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树，哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
从这个角度来说，带权路径最短才是哈夫曼树，那就是唯一的。从严格数学逻辑推理没有证明过，所以这个只供参考。
15 3 14 2 6 9 16 17 构造的哈夫曼树是：
82
/ \
33 49
/ \ / \
16 17 20 29
/ \ / \
9 11 14 15
/ \
5 6
/ \
2 3
WPL = （2 + 3）* 5 + 6 * 4 +（ 9 + 14 + 15 ） * 3 + （16 + 17）* 2 = 229