哈夫曼树是否唯一 _哈夫曼树是否唯一

哈夫曼树不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
哈夫曼树(Huffman)树又称最优二叉树，是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径，路径上的分支个数称为路径长度。二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。如果二叉树中的叶子结点都有一定的权值，则可将这一概念。
设二叉树具有n个带权值的叶子结点，则从根结点到每一个叶子结点的路径长度与该叶子结点权值的乘积之和称为二叉树路径长度，记做：WPL=W1L1+W2L2+WnLn等等；其中：n为二叉树中叶子结点的个数；Wk为第k个叶子的权值；Lk为第k个叶子结点的路径长度。
赫夫曼树是否唯一不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree) 。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
历史：
1951年，哈夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。
由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。
哈夫曼树是否唯一哈夫曼树不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
哈夫曼树(Huffman)树又称最优二叉树，是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。从树中一个结点到另一个结点之间的分支构成了两结点之间的路径，路径上的分支个数称为路径长度。二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。如果二叉树中的叶子结点都有一定的权值，则可将这一概念。
设二叉树具有n个带权值的叶子结点，则从根结点到每一个叶子结点的路径长度与该叶子结点权值的乘积之和称为二叉树路径长度，记做：WPL=W1L1+W2L2+WnLn等等；其中：n为二叉树中叶子结点的个数；Wk为第k个叶子的权值；Lk为第k个叶子结点的路径长度。
给定一组权值，可以唯一构造出一棵哈夫曼树ma?不唯一，因为没有限定左右子树，并且有权值重复时，可能树的高度都不唯一，唯一的只是带权路径长度之和最小。
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
【哈夫曼树是否唯一】扩展资料：
一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1 。
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
一个结点的权值实际上就是这个结点子树在整个树中所占的比例.abcd四个叶子结点的权值为7，5，2，4，这个7，5，2，4是根据实际情况得到的。
比如说从一段文本中统计出abcd四个字母出现的次数分别为7,5,2,4. 说a结点的权值为7，意思是说a结点在系统中占有7这个份量。实际上也可以化为百分比来表示，但反而麻烦,实际上是一样的。