sjbird331 发表于 2007-12-19 09:11

【求助】哈夫曼树的构造

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

wjjqw_123 发表于 2007-12-21 12:50

回复

顺序是有关系的,有左右之分。这个特别要注意。

logan0429 发表于 2007-12-21 16:57

其实我也碰到这样问题，不过上课时老师都是选两个最小和次小的分别作为左孩子和有孩子，因为定义是按wpl最小的成为赫夫曼树，所以次序不一样应该没有关系的

ynlm 发表于 2007-12-27 18:21

我觉得都差不多，但要注意一致性，也就是说译码时也要有相同的二叉树，如果你编码时把最小的放在左边，对方译码时如果把最小的放在右边就会出错。所以最好还是统一把最小的放左边，次小的放右边。这样就不会出错。

lajiya 发表于 2007-12-27 19:02

定义不同所致吧

sunkaidong 发表于 2007-12-27 20:31

谁能给代码出来看看啊,关于树的建立和遍历.

sjbird331 发表于 2007-12-28 21:46

谢谢你们的热心帮助啊

米车阿里 发表于 2007-12-29 11:39

我有个贴子就是关于哈夫曼编码和解码的，不知道对你有没有用
[url]http://bbs.bc-cn.net/thread-188704-1-1.html[/url]

syuanq 发表于 2007-12-29 18:28

哈夫曼树构造不是唯一的，所以出现左右不一样是可以的

hi-20000 发表于 2008-1-1 16:38

主要是ＷＰＬ要求是最短才是正确的，如果不是最短的就有问题了！
还有左右要分一下，主要是编译代码时防止出错

页: [1]

编程论坛