知道了苦逼IT女还得去“种树”——苦逼IT女种树记之哈夫曼树

        啦啦啦啦，好不容易种好了二叉树，继续努力种哈夫曼树咯。胡哥说了：树，是一种重要的结构，这样说吧，你想想，一个学校是不是一棵树，我们一个岳麓区是不是一棵树，还有一个多线程的游戏是不是一棵树…………所以在我们的日常生活中，树是一种重要的结构，将树和日常的生活联系在一起，可以便于理解树的概念和发现树的重要性，也更加重视树。既然酱紫，那我们赶紧来种树吧~~好开心地去种树啦~~

 

       今天呢，我们要种的树是哈夫曼树，这个树和二叉树一样不好种，甚至更难，有一点是：二叉树的构成方法、规则我们可以人为地规定，而哈夫曼树则是确定方法和规则的，其实哈夫曼树也是二叉树的一种，哈夫曼树又被称为最优二叉树是一种带权路径长度最短的二叉树。

       下面详细介绍一下：

                 树的带权路径长度：树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）；

                 树的路径长度：从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。

 

       当然，哈夫曼树的构造方法才是重点，下图形象地表示了构造方法：

 

 

       当我们知道了其构建方法后，似乎一切就都简单了，我也曾天真滴这样以为，以为离散里面学了的，会有优势，后来才发现，已经被离散里面的理论思想给禁锢了，在实践上也就寸步难行了。不过在一步一步的慢慢实践中，也就慢慢掌握了。

       当构建好树之后，就得编码了，这才是我们的目的，根据整组数据中符号出现的频率高低，决定如何给符号编码。如果符号出现的频率太高，则给符号的码越短，相反符号的号码越长。这得记住哈夫曼树编码的规则是“左0右1”，遍历递归输出编码就可以得到编码了。这也就是文件处理中的压缩处理。

       然后还有个根据编码得到原来的树，这就是一个解压的过程。

       理论的说了这么多了，重要的其实还是实践，在下现在的实现方式还有点问题，不过现在调试ing，所以代码就不贴啦，还得继续种树去，种树大业，任重道远！

       一个不聪明的程序猿应该比一般人更刻苦，更何况我一只笨笨滴程序猪呢，对自己说：继续努力吧~！