haffman树的实现

整体分析：

• 首先，我们要分析一下整体思路，我们分成三个部分，第一部分是建树，第二部分是应该做的是得到一个字符串后把它变成一个01二进制，再把一个01二进制变成一个字符串，第三部分则是建立文档来读取和存储。
• 然后考虑到第一部分，我们可以分成几步，第一步，我们把字符串中的字符个数统计出来，第二步，建立一定的节点，第三步，把这些节点连成一棵树。
• 接着是第二部分，其实这个可以不在haffman class里做了，可以在主调用的方法里做。它们也是分为三步走，第一步是根据这个树把建立字母与01的对应关系，第二步是根据对应关系加密，第三步是解密。

• 最后就是建文件了，这个很简单。

  第一部分：建树

  第一步：统计字符个数

  ??我们可以采用一种简单粗暴的方法，直接用数组来存，我们可以注意到的是我们在一般的使用过程中我们可以用方法来让这些字母与数组一一对应，当然，我们也可以通过a.charAt(i)-‘a‘的形式来确定每一个字符在数组中的位置，然后在每碰到一次这个字母让那个对应的数自增一次就好了。我这里采用的是第一种方法。

??在这之后我们可以得到一个记录每个字母个数的数组。
??然后，我们在中间加半步，我们新建一个数组用来存哪些字母是存在，哪些字母是不存在的这样方便在后面建树的时候立减少浪费。

第二步：建立节点

??有了这个数组b后，我们建立节点也就有了根据，我们可以根据这些来建立节点。

第三步：连接这些节点

??其实这一步才是大头所在，也主要容易卡在这一步。我们可以看到的是，我们已经有了这么多节点，那么我们的当务之急是把这些节点都连接起来（废话）根据它成树的原理，我们可以想到的是每一次我们都取出数字最小的两个节点，然后把它们加在一起形成一个新的节点放进去，其实第一眼我的想法是这不就是优先队列吗，想直接上手，但发现好像不会用java里的优先队列，就只好先用队列代替。每次pop出一个数，与现有的两个数比较，留下较小的两个数，把大数push回去，这样弄一轮就可以把选出最小的两个数，然后操作之后再把和放回去，直到只剩一个。

第二部分：加密、解密

第一步：建立对应关系

??这个其实也是一个遍历的事，注意的是我们这里尽量用递归的方法，这样就不用来回增删末尾元素。

第二步：加密

??这一步我们要做的是把字符串扫描一遍，扫描同时对每一个字符进行加密。

第三步：解密

??这个比较有趣，我们直接由字符串对树进行操作，由01确定是左还是右子树，然后把已经走过的01去掉。

第三部分：建文件

haffman树的实现

原文：https://www.cnblogs.com/ydfy/p/11899416.html