如何实现哈夫曼树在文件压缩和加密中的应用代码？

本文共计1998个文字，预计阅读时间需要8分钟。

在先前编写LZW压缩算法时，遇到了许多难以解决的问题。基本上，都在哈夫曼编码中得到了解决。然而，写这代代码实在费神，但最终还是完整地跑出了代码。最终，哈夫曼树这个想法确实很牛。

在以前写LZW压缩算法的时候，遇到很多难受的问题，基本上都在哈夫曼编码中解决了，虽然写这代码很费神，但还是把代码完整的码出来了，毕竟哈夫曼这个思想确实很牛逼。哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题，就是压缩后文本的分割。比如用lzw编码abc，就是1,2,3。但这个在存为文件的时候必须用分割符把1,2,3分割开，非常浪费空间，否则会和12 23 123 产生二义性。而哈夫曼树，将所有char分布在叶节点上，在还原的时候，比如1101110，假设110是叶节点，那么走到110的时候就可以确定，已经走到尽头，回到根节点继续走，这样就避免了字符的分割，全部用1010101010101这样的路径表示字符，可以将8位压缩为1个char进行存储。在构造树的时候，将出现率高的char放在上面，这样路径就很短，自然就节省了存储空间。虽然哈夫曼压缩效率不是最高的，但还算比较乐观的。

哈夫曼除了压缩以外还可以用于加密，在将文本用哈夫曼编码时，需持久化生成的char计数链表结构，这样才能还原出树结构，而解码时路径正是依赖于树结构的。也就是说，这种编码是属于约定形式的编码，在编码时用原文本产生树结构，而存储的是树路径，解码的时候缺少树或树结构与原先不相符都是无法完成解码的，就好比，我用10代表a，你存的是10，你将10解释为 b或c等等都是不正确的。