hdu 1053 Entropy (哈夫曼树)

（1）建立哈夫曼树节点结构体

<a></a>

（2）首先我们把读入的字符串进行预处理，按照字符分别放入对应的节点中，同时记录其出现频率，count_num记录字符出现次数，同时放入哈夫曼节点中

（3）用一个优先权队列存储节点，每次取出频率最小的两个节点，合并节点并把其合并后的节点放入优先权队列中，一直合并到队列中只剩下最后一个节点，把其作为根节点。（这正是哈夫曼树建立的关键，这个地方一定要理解）

（4）哈夫曼树建立完之后就是求其编码长度的问题了，这时候就是遍历该树的问题了，方法有很多，可以深度遍历，也可以广度遍历。这里采用广度遍历，同时借助于一个queue进行的。

（5）剩下的就很简单了，不做过多的赘述。

整个题的全部代码

本文转自NewPanderKing51CTO博客，原文链接：http://www.cnblogs.com/newpanderking/archive/2012/11/14/2769367.html ，如需转载请自行联系原作者