哈夫曼树构造
问题描述：
哈夫曼树构造
哈夫曼树的权值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树时都为节点排序.即使这样结果也不唯一.