中文XML论坛--[求助]哈夫曼树的构造

贴子主题： [求助]哈夫曼树的构造

本主题类别:

近几天做了一些哈夫曼树的问题，发现有的参考书中对于哈夫曼树的构造问题存在不同的理解，这种理解造成了我在做题时的困惑。现在就把这些困惑的地方写出来，希望有兴趣的朋友能给我解答，谢谢
（1）有的参考书上说，从给定序列T中选取权值最小的和次小的作为合并之后树的左、右孩子；而还有一些参考书则直接没有这种规定，直接选取较小的两个结点，而对于谁为左、右孩子，则没有规定。请问在实际的哈夫曼树构造过程中，我们应该遵循一个什么样的原则进行合并呢？
（2）我做的一些题中，总是存在这样一个问题：构造完成后的哈夫曼树的带权路径长度总是正确的，但是构造之后树的结构和答案给出的哈夫曼树的结构存在一些差异，这种差异体现在原序列中结点的次序不对，比如说，答案中结点3和结点4分别为合并之后树的左、右孩子，但是我做出来的却是结点4和结点3分别为左、右孩子。请问，这种差异是正常的还是不正常的，WPL一样，但是结点的相对次序不一样（当然，对应的结点总是在同一层）
请大家帮我想想这是怎么回事，谢谢


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	46.875ms