哈夫曼树

哈夫曼,本身是一种压缩算法。她是怎么压缩的我也不知道,反正就是这样。

举个例子,如果有100个学生,他们的得分统计规则,小于60得到E,60-70分得到D,70-80分得到C,80-90分得到B,90-100得到A。

100个学生的得分概况如下:A 5人,B 15人,C 40人, D 30人,E 10人

正常的代码如下:

经过哈夫曼算法,调整之后的代码:


哈夫曼之后的算法,比之前的算法计算的速度要快。

如何构建一棵哈夫曼树:

如下图所示:

构建哈夫曼树的原理:

1.将带权重的叶子节点,有小到大排序。

2.在排序的列表中取出来两个最小的,作为叶子节点,他们的两个组成的新的根节点(他的权重为两个叶子节点的和),放到原列表中。在重新计算,最后得到的一棵树,就是哈夫曼树,权重越大,越是靠近根节点。


哈夫曼如何编码编码


打印哈夫曼编码的原理:

如果想打印node F的哈夫曼编码,只要找到他的父节点,如果是父节点的左孩子,就像栈中压栈0,如果是右孩子就压栈1.节点向上移动,直到是root节点位置。最后再将栈中的元素0或者1打印出来就行了。利用了栈的先进后出的原则。

代码如下:


HuffmanTree.java

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容