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

发布网友发布时间：2022-04-28 10:32

我来回答

共5个回答

热心网友时间：2023-09-26 08:05

肯定不唯一：

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

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

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

可以画成这样：

取a 的代码就是：1101

第二种画法：

a= 10110

还有其它画法 a=010

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

热心网友时间：2023-09-26 08:05

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

热心网友时间：2023-09-26 08:06

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

热心网友时间：2023-09-26 08:06

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

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

热心网友时间：2023-09-26 08:07

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

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