一棵哈夫曼树在不同的人之间会有所不同吗？
我需要为一个大学项目制作一棵哈夫曼树，但我真的很困惑它是如何工作的。我实现了哈夫曼树的编码部分，但它始终与http://huffman.ooz.ie/不同。
一个人向另一个人编码可能会有所不同，但正确吗？
Mar*_*ler 10
是的。
首先，您可以任意将 0 和 1 或 1 和 0 分配给树的每对分支，以获得同等有效的代码。
其次，在霍夫曼算法的每个步骤中查找最低频率组时，您可能会遇到最低频率由三个或更多组共享的情况，或者第二低频率由两个或更多组共享的情况。然后，您可以选择在该步骤中合并哪些组。在这种情况下，您最终可能会得到不同的相邻符号，甚至拓扑不同的树，所有这些都是同样最佳的。
对于链接的示例，第一步中有五个频率一符号可供选择，从而导致第一次配对有十种不同的选择。然后在第二步中有三个频率一符号可供选择，第二次配对有三种不同的选择。因此，马上就会有 30 棵不同的树，并分配有可以构建的符号。
这些在拓扑上都是等效的。第三步变得更有趣，第二低频率有三种选择，其中两个是分支，一个是叶子。因此可能会产生两种不同的拓扑。
总之，该特定频率集可以产生 24 个拓扑不同的树，为每个拓扑乘以大量不同的符号和比特分配。因此，事实上，您最终得到与示例中所示完全相同的树的概率应该非常小！
以下是频率 {1, 1, 1, 1, 1, 2, 3, 3, 3, 3, 3, 4, 5, 5, 6, 7, 9, 10, 12, 16} 的 24 种可能的拓扑：
