我怎么知道我的霍夫曼树是否正确？
How do I know if my huffman tree is correct?
问到的问题：
Create a Huffman tree and codes for the following numbers: 24, 55, 13,
67, 88, 36, 17, 61, 24, 76
所以我创建了这棵树：
但是因为可能有多个树，我怎么知道我的树是否正确，因为有多个元素具有相同的频率？
Interpreting the "numbers" as symbols as opposed to frequencies, we then have the set of frequencies {1, 1, 1, 1, 1, 1, 1, 1, 2}. Due to having more than one choice at some of the steps in the Huffman algorithm, there is more than one possible resulting topology. Here are the three topologically distinct trees you can get, depending on the choices you make:
For each of those, you can arbitrarily choose which of your symbols to put at each length. For the first two trees, the 2 has to be symbol 24, but the remaining eight symbols can be split however you like among each group of four. For each of those two trees, that is 70 possible unique length assignments. For the third tree, again the 2 has to be symbol 24, but the remaining symbols can be split as you like into the groups of two and six, for 28 possible choices.
Having made those choices, you now can assign codes to each leaf, where at each branch you can independently and arbitrarily assign 0 to the left branch and 1 to the right branch, or 1 to the left branch, and 0 to the right branch. For each tree and symbol lengths assignment, that gives 256 possible code assignments.
All told, there are 43,008 possible codes that can result from the Huffman algorithm. All of these choices are correct. They all result in the same optimal number of bits in the message (32).
Here is .
问到的问题：
Create a Huffman tree and codes for the following numbers: 24, 55, 13, 67, 88, 36, 17, 61, 24, 76
所以我创建了这棵树：
但是因为可能有多个树，我怎么知道我的树是否正确，因为有多个元素具有相同的频率？
Interpreting the "numbers" as symbols as opposed to frequencies, we then have the set of frequencies {1, 1, 1, 1, 1, 1, 1, 1, 2}. Due to having more than one choice at some of the steps in the Huffman algorithm, there is more than one possible resulting topology. Here are the three topologically distinct trees you can get, depending on the choices you make:
For each of those, you can arbitrarily choose which of your symbols to put at each length. For the first two trees, the 2 has to be symbol 24, but the remaining eight symbols can be split however you like among each group of four. For each of those two trees, that is 70 possible unique length assignments. For the third tree, again the 2 has to be symbol 24, but the remaining symbols can be split as you like into the groups of two and six, for 28 possible choices.
Having made those choices, you now can assign codes to each leaf, where at each branch you can independently and arbitrarily assign 0 to the left branch and 1 to the right branch, or 1 to the left branch, and 0 to the right branch. For each tree and symbol lengths assignment, that gives 256 possible code assignments.
All told, there are 43,008 possible codes that can result from the Huffman algorithm. All of these choices are correct. They all result in the same optimal number of bits in the message (32).
Here is