如何解决哈夫曼树不唯一的问题?

Huffman树是不是唯一的？B－树是不是唯一的？？~

Huffman树是不唯一的，B-树是什么啊

不可以。因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
哈夫曼树（霍夫曼树）又称为最优树.
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

肯定不唯一：

一个string 的哈夫曼树有多种画法

例如："a fast runner need never be afraid of the dark"

一共46个字符： 按字符出现频率从大到小排列：

可以画成这样：

取a 的代码就是：1101

第二种画法：

a= 10110

还有其它画法   a=010

我翻阅了所有的资料真的还没有发现一种哈夫曼树的唯一画法，画法既然多种，高度肯定不一样，代码肯定也不一样。请点击输入图片描述

哈夫曼树不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
哈夫曼树(Huffman)树又称最优二叉树，是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径，路径上的分支个数称为路径长度。二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。如果二叉树中的叶子结点都有一定的权值，则可将这一概念。
设二叉树具有n个带权值的叶子结点，则从根结点到每一个叶子结点的路径长度与该叶子结点权值的乘积之和称为二叉树路径长度，记做：WPL=W1L1+W2L2+WnLn等等；其中：n为二叉树中叶子结点的个数；Wk为第k个叶子的权值；Lk为第k个叶子结点的路径长度。

哈弗曼树可以不唯一，但是他们具有相同的带权路径长度。
另外，哈弗曼编码才是唯一的。请将这两者（哈弗曼树和哈弗曼编码）区分开！

绝对是唯一的。
1、理解概念含义
2、操作过程中不要出错

只有唯一性，才会保证哈夫曼编码与解码的成功。
绝对的

绝对是唯一的。
1、理解概念含义
2、操作过程中不要出错

只有唯一性，才会保证哈夫曼编码与解码的成功。

---

萧山区17827038436： 如何解决哈夫曼树不唯一的问题? - ？
翁饶莫匹： 绝对是唯一的. 1、理解概念含义 2、操作过程中不要出错 只有唯一性,才会保证哈夫曼编码与解码的成功. 绝对的

萧山区17827038436： 赫夫曼树是否唯一 - ？
翁饶莫匹： 不唯一,因为没有限定左右子树,并且有权值重复时,可能树的高度都不唯一,唯一的只是带权路径长度之和最小. 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为...

萧山区17827038436： 哈夫曼树,一定要按照同层节点权值由小到大的次序构造?如果我不按从小到大的话,哈夫曼树岂不是不唯一了?到底有什么规则没有哦? - ？
翁饶莫匹：[答案] 没有规定说哈夫曼树构造出来时唯一的,哈夫曼编码只是为了让带权路径达到最小,所以,同层不按大小排序,对树的带权路径没有影响,也就是编码长度没有变化,变化的只是编码的值变了,如: 3 3 / \ / \ A1 B2 B2 A1 A的编码本来是0,B是1,变...

萧山区17827038436： 哈夫曼树编码一定是左边为0,右边为1吗? - ？
翁饶莫匹： 注:0和1表示左子树还是右子树没有明确规定.因此左右节点的顺序是任意的,所以构造出的哈夫曼树并不唯一,但是各个哈夫曼树的带权路径长度相同且为最优.

萧山区17827038436： 哈夫曼编码问题请教; - ？
翁饶莫匹： 两个最小的编码没有左右之分.是不同,哈夫曼编码不是唯一的,但是它们的WPL(带权路径长度)都是一样的.如果,最下面有两个二叉树,那么也不用考虑左右的问题,你只将最下面两个二叉树当作两个节点就可以了.记住:哈夫曼编码不...

萧山区17827038436： 求解赫夫曼树的问题 - ？
翁饶莫匹： ①首先把 n 个叶子结点看做 n 棵树(仅有一个结点的二叉树),把它们看做一个森林.②在森林中把权值最小和次小的两棵树合并成一棵树,该树根结点的权值是两棵子树权值之和.这时森林中还有 n-1 棵树.③重复第②步直到森林中只有一棵为止.很高兴为您解答,祝你学习进步!如果您认可我的回答,请点击下面的【选为满意回答】按钮!有不明白的可以追问!

萧山区17827038436： 哈弗曼树是唯一的吗? - ？
翁饶莫匹： 哈弗曼树是带权路径长度最小的树,所以是唯一的,但是哈弗曼编码不唯一,是不是这么理解?但是谁做左子树,谁做右子树的法则问题还是没人回答啊,是不是权值小的做左子树? 查看原帖>>

萧山区17827038436： 【数据结构】关于画哈夫曼树的问题 - ？
翁饶莫匹： 不一定,但wpl相同你的与书上的方法是不同的吧相同的方法是唯一的只要wpl最小就是最优的吧一般我们总是取当前根节点最小的两棵树合并的2 3 4 7 8 9第一次二三合并为55 4 5 7 8 92 3 第二次4 5 合并为99 7 8 95 4 2 3第三次7 8合并为 15 15 9 9 7 8 5 42 3第四次 9 9合并 18 15 9 9 7 84 52 3第五次 18 15 合并 3118 159 94 52 3吧

萧山区17827038436： 哈夫曼树？
翁饶莫匹： 这么明确的算法,肯定唯一,数如下: 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:1110 0.09:1111 0.13:110 0.21:00 0.23:01 0.27:10 没有谁是谁的前缀,OK. 针对补充问题: 不行,生...

萧山区17827038436： 怎样证明:一棵有n个叶子的哈夫曼树共有2n - 1个结点? - ？
翁饶莫匹：[答案] 我的理第1次必定是2个叶子组成二叉树,产生1新结点,接下来有2种情况: 1.此新结点与原剩下的叶子再组成二叉树又产... 所以实际上数量与第1种一样,共有2n-1个. 具体证明用一个构造哈夫曼树的算法.