哈夫曼树构造

题目

哈夫曼树构造
哈夫曼树的权值2,1,4,5,7,3,4,9所构造出来的哈夫曼树.
35 35
/ /
20 15 20 15
/ / / /
11 9 8 7 9 11 7 8
/ / / /
6 5 4 4 5 6 4 4
/ /
3 3 3 3
/ /
2 1 1 2
这两个构造出的书那一个是对的.还是都是对的.哈夫曼树是应该权值小的在左边权值大的在右边吗?还有比如说一组权为2 3 5 11 12的数列构造哈夫曼树 10 10
/ 还是 /
5 5 5 5
/ /
2 3 2 3
请问这两个哪个对还是都对.

答案

Huffman树本身的定义没有规定两棵子树的权值排序,所以两棵都是Huffman树.
但结构化的Huffman算法生成的Huffman树子树都是有序的.所以一般生成Huffman树时都为节点排序.即使这样结果也不唯一.