哈夫曼树

写这篇博客源自于之前做了一道哈夫曼编码的题，但是当时哈夫曼树的知识已经遗忘了，因此没有做出来。后来在学习左神的算法的时候，复习到了切金条的问题，其中用到了哈夫曼树，因此趁此机会在网上学习了哈夫曼树的相关知识并自己动手用Java实现了相关操作，记录在博客中，方便日后查阅。

参考博客：https://www.cnblogs.com/kubixuesheng/p/4397798.html

什么是哈夫曼树

要学习哈夫曼树，首先要知道哈夫曼树是什么，为什么要用哈夫曼树。

问题场景：判断结构

如果要使用条件判断将百分制成绩转换为等级输出，可以写多个if else语句，将其判断逻辑用一个树来表示，其中越接近树顶层的结果越容易获取到，假如有如下的分数段分布情况

分数	0-59	60-69	70-79	80-89	90-100
比例	0.05	0.15	0.40	0.30	0.10

为了写出判断每个学生分数区间的代码，可以有如下两种构造方式

构造方式1

构造方式2

这样第一种方式的判断次数要多余第二种方式，原因是假设头节点高度为0，越往下高度越高，节点所在的高度越高，则找到此节点所需要的工作量越大。这时候为了找到一种效率最高的判别树，便找到了哈夫曼树。

哈夫曼树有关概念

路径：在一棵树中，从一个结点到另一个结点的通路。

路径长度：路径上的结点个数-1。

结点的权：路径上的值，可以理解为节点的距离，通常指字符对应的二进制编码出现的概率。

树的路径长度：从树根节点到每一个叶结点的路径长度之和。

结点的带权路径长度：该结点到树根的路径长度与该结点上权的乘积

树的带权路径长度：所有的结点带权路径长度之和。

哈夫曼树就是树的带权路径长度最短的二叉树。

如何得到一棵哈夫曼树

哈夫曼树构造算法

1. 根据给定的带权值的结点构成二叉树集合，每个二叉树只有一个带权值的结点，左右子树为空
2. 在集合中选取权值最小的两个二叉树重新构造一个二叉树，新的二叉树的权值为两个二叉树权值之和
3. 在集合中删除取出的两个二叉树，将新的二叉树放入
4. 重复步骤2,3直到只有一棵二叉树

这样便得到了一棵哈夫曼树。

要注意的是，具有相同带权结点的哈夫曼树不唯一。

哈夫曼树的应用

哈夫曼编码

哈夫曼编码为哈夫曼树在通讯领域的应用，可以有效压缩数据，在编码时候需要考虑两个问题：数据的最小冗余编码（频率大的字符编码短），译码唯一性（一个译码对应唯一编码），利用哈夫曼树可以很好解决以上问题。

在之前介绍的哈夫曼树构造基础之上，在两个子树合并为一个新的二叉树时，选择权值较小的二叉树为左子树，然后从树的根结点出发，其左子树的分支标‘0’，右子树的分支标’1’，这样便可以得到每个字符的编码，如下图所示

这样得到的编码即为二进制前缀编码。

总算将其基本概念大致介绍了一遍，那么开始从最初的起点（做错的题）开始，自己设计一个用于26个英文字符编码的哈夫曼树吧！

”我的”哈夫曼树

问题介绍

假设某段通信电文仅由 6 个字母 ABCDEF 组成，字母在电文中出现的频率分别为2，3，7，15，4，6。根据这些频率作为权值构造哈夫曼编码，最终构造出的哈夫曼树带权路径长度与字母 B 的哈夫曼编码分别为__。(这里假定左节点的值小于右节点的值)

因此接下来的内容为致力于构造自己的哈夫曼树，来解决此类问题。

需求介绍

在明确了问题后，需要进一步分析需求。

输入：目前看到关于哈夫曼树的题目有两种输入方式，一种是直接输入一串字符串，另一种是逐个输入字符，频率。

输出：希望最后输出有哈夫曼树的路径长度，带权路径长度与每个字母对应的哈夫曼编码。

因此便得到了基础需求，即输入字符串或者字符+频率，得到其对应的哈夫曼树路径长度、带权路径长度与哈夫曼编码，下面将逐步实现这些需求，并在此基础之上，增加一些自定义的需求。说明：下面定义的哈夫曼树基于大写英文字母进行统计，只进行A-Z的字符统计。

树结点的结构

树由结点构成，基本的树结点中有值，左结点，右结点，而为了实现需求，需要在此之上加入每个节点的字符，结点的值为每个字符的频率，而当集合中有多个子树权值相等时，为了让树显得更加饱满（高度更低），选择优先让子结点数更少的二叉树进行合并，因此需要加上当前结点下所有结点的个数（包括自己），因此树结点的定义如下

class HaffNode{
    public Character c;//字符
    public Integer fre;//频数
    public Integer count;//子结点个数
    //两个结点
    public HaffNode left;
    public HaffNode right;
    public HaffNode(Character c, Integer fre, int count){
        this.c = c;
        this.fre = fre;
        this.count = count;
    }
}

哈夫曼树的结构

在前面所介绍的哈夫曼树的生成算法中，每次需要弹出两个权值最小的两个子树，最后直到只有一个子树，因此可以利用小根堆来实现，在Java中的实现为优先级队列PriorityQueue，为了保证让子结点树更小的二叉树优先被弹出，定义相应的比较器

class HaffmanCompare implements Comparator<HaffNode>{
    //让树更均衡
    @Override
    public int compare(HaffNode o1, HaffNode o2) {
        return o1.fre != o2.fre ? o1.fre - o2.fre : o1.count - o2.count;
    }
}

核心思想为如果两个二叉树权值不同，则优先比较权值；若权值相同，则优先弹出子树个数更少的二叉树。

然后将此比较器传入哈夫曼树中维护的优先级队列中，因为在需求中介绍了有两种输入方式，一种为直接传入字符串，一种为逐个传入字符和频数，因此相应的定义了两种构造函数，一种有参数的对应传入字符串，一种无参数的对应逐个传入字符。

class MyHaffman {
    //持有小根堆，用来统计每个字符的个数
    private PriorityQueue numHeap = null;
    private String str = null;
        public MyHaffman(String str){
        numHeap = new PriorityQueue(new HaffmanCompare());
        this.str = str;
    }
        public MyHaffman(){
        numHeap = new PriorityQueue(new HaffmanCompare());
    }
}

在完成了树的初始化后，需要将每个字符与其频率封装成为结点对象，传入维护的优先级队列中。因此首先需要统计每个字符与其频率

统计每个字符与其频率

传入字符串

首先介绍传入参数为一个字符串的形式，假设传入字符串为“ABACCDA”，为了统计每个字符串个数，可以利用桶排序，即维护一个长度为26的数组作为桶，若为A在0号桶，为B在1号桶，以此类推。这样便可以将每个桶位置处的字符个数统计出来。然后遍历桶的26个位置，如果当前桶中有数，就将此位置对应的字符与其频率封装成结点对象，并放入堆中。

其中封装的时候，传入当前字符，频率，所有结点个数（1）。

//输入字符串，统计频率，并加到大根堆中
public void getFre(){
    //桶排序，将每个字符放入桶中
    int[] arr = new int[26];//统计频率
    for (int i = 0; i < str.length(); i++) {
        arr[str.charAt(i)-'A']++;
    }
    //从桶中取出来数，统计每个字母的个数
    for (int i = 0; i < 25; i++) {
        if (arr[i] != 0){
            System.out.print((char)('A'+i)+" "+arr[i]+" ");
            numHeap.add(new HaffNode((char)('A'+i),arr[i],1));
        }
    }
    System.out.println();
}

传入数组

而如果是以A 3，换行，B 4,…，这样的形式输入，则在输入的函数处维护一个数组，数组的index为0的地方表示A，值为3，表示A的频率为3，以此类推，便得到了一个字符的频率数组，完成此过程的代码如下

//传入字符和频数来构造数组
public void addCharAndFre(int[] arr,char c, int fre){
    //新建桶，放入桶中
    if (c < 'A' || c > 'Z' || fre <=0)
        throw new RuntimeException("输入的字符不为A-Z之间或者频数不为正数");
    arr[c-'A'] = fre;
}

将所有的输入都存到了上述数组中后，便可以遍历桶，将不为0处对应的字符与频率封装为结点对象并放入堆中。

public void getFre(int[] arr){
       //从桶中取出来数，统计每个字母的个数
       for (int i = 0; i < 25; i++) {
           if (arr[i] != 0){
               System.out.print((char)('A'+i)+" "+arr[i]+" ");
               numHeap.add(new HaffNode((char)('A'+i),arr[i],1));
           }
       }
       System.out.println();
   }

接下来便可以开始构造哈夫曼树

树的构造

这方法需要返回树的根结点，其思路为

1. 如果堆为空，返回空
2. 如果堆中元素比1大，则弹出2个结点
3. 新建一个结点，字符为A-Z之外的（此处选#），权值为两个子树之和，左子树为权值较小的，总结点树为两子树结点树之和+1
4. 将此结点重新放入堆中，继续步骤2,3，直到只有1个结点
5. 返回此结点，即为哈夫曼树的头结点

//构建哈夫曼树
private HaffNode getHaffTree(){
    //如果堆为空，返回空
    if (numHeap.isEmpty())
        return null;
    //从numHeap中弹出两个，构建新的节点，再丢进去
    while (numHeap.size() > 1){
        HaffNode cf1 = numHeap.poll();
        HaffNode cf2 = numHeap.poll();
        //字符用单引号
        HaffNode res = new HaffNode('#',cf1.fre+cf2.fre,cf1.count+cf2.count+1);
        //构建左右子树
        res.left = cf1.fre <= cf2.fre ? cf1 : cf2;
        res.right = cf1.fre <= cf2.fre ? cf2 : cf1;
        numHeap.offer(res);
    }
    //只剩一个的时候弹出
    return numHeap.peek();
}

树的打印

为了直观显示树的结构和方便验证程序的正确性，此处直接使用左神的打印树的函数，其核心思路为递归方式的中序遍历，每一层树占据的长度为len，因此需要计算得到每个结点所在树的高度，如果为右子树，用V标识；如果为左子树，用^标识。递归的中序遍历为递归左子树，打印当前结点，递归右子树。

//打印树
    public static void printTree(HaffNode head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }
    public static void printInOrder(HaffNode head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.c + head.fre + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }
    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

树的编码

在构建好树以后，需要得到每个叶子结点的编码。思路为递归实现，需要传入的参数是统计结果的Map，用来表示当前路径长度的String，用来表示总的带权路径长度的StringBuilder，以及当前树的高度和当前结点。

采用先序遍历，base case为结点为空，当结点不为空的时候：

1. 如果当前结点为叶子结点，将其字符编码加入，将其带权路径加入到结果中（如果StringBuilder长度为0，直接将当前高度*频率加入；若已经有数，将之前的数取出，累加上当前结点的带权路径长度，替换到StirngBuilder中原来的值）
2. 如果当前结点不为叶子结点，递归遍历其左子树，其中string加上0，高度加一
3. 递归遍历其右子树，string加上1，高度加一

在此过程中遇到的坑有，之前为了获得结点的字符使用的是StringBuilder类型，但是因为StringBuilder的值在堆中而不是在当前递归栈中，在返回到上一级时需要将当前步骤的影响消除，使用此方法效果有问题。后在leetcode上找到了相似的题目，使用String类型来保存当前栈的状态，这样不用自己去手动消除这一步状态 ，更为简单。而计算带权路径又需要一个堆内存中的变量，此处使用比较笨的方法，利用StringBuilder，每次取出之前的值，加上当前值再进行替换。其中使用的replace函数来替换，起始位置为0，终止位置要是其长度。

得到的启示：要是遇到要获取每个结点的路径的题目，可以使用String类型来保存其路径，这样可以自动随栈变化，使用比较方便。

//编码，使用StringBuilder有问题，现在改成String
public void encodingHaff(Map map, String sb, StringBuilder num, int height, HaffNode cf){
    //basecase
    if (cf != null){
        //当前节点为叶子节点
        if (cf.left == null && cf.right == null){
            //将答案加入
            map.put(cf.c,sb);
            if (num.length() == 0){
                num.append(height*cf.fre);
            }else {
                int temp = Integer.valueOf(num.toString())+height*cf.fre;
                num.replace(0,num.length(),String.valueOf(temp));
            }
        }else {
            //如果不为叶子节点，遍历左右两边
            encodingHaff(map,sb+0, num, height+1, cf.left);
            encodingHaff(map,sb+1,num, height+1, cf.right);
        }
    }
}

同时需要实现给一个字符串，输出其编码后的二进制码，思路为字符串每一位在Map中进行寻找，最后输出

//输入字符串，给编码后的二进制码结果
public String codeHaff(String str, Map map){
    if (str == null)
        return null;
    StringBuilder res = new StringBuilder();
    for (int i = 0; i < str.length(); i++) {
        res.append(map.get(str.charAt(i)));
    }
    return res.toString();
}

树编码结果的输出

在上一步中，树所有的编码结果放在了一个Map中，因此需要获取Map中的所有数，比较old school的方式是先获取Map的EntrySet类型的Set，再获取Set的EntrySet类型迭代器，利用迭代器来遍历Map，获取其每一个Key与Value，为了让程序更有拓展性，此处使用了泛型。

//遍历map
   public  void itraMap(Map map){
       //得到entey
       Set> entrySet = map.entrySet();
       //遍历enterset
       Iterator> it = entrySet.iterator();
       while (it.hasNext()){
           Map.Entry me = it.next();
           K key = me.getKey();
           V value = me.getValue();
           System.out.println(key+":"+value+" ");
       }
   }

也可以使用更加简洁的写法，用 foreach语句遍历map的keySet，如下

//遍历map的较方便写法
public  void itraMap2(Map map){
    for (K key : map.keySet()){
        V value = map.get(key);
        System.out.println(key+":"+value+" ");
    }
}

这时候基本需求便实现了，但是获取了编码，如果给出了一串编码后的结果，该如何得到其解码呢？

因为哈夫曼树为二进制前缀编码，当编码规则确定后，解码结果应该唯一。因此，如果给定了一个字符串输入，从第一个字符开始看，在根结点开始遍历，如果是0，去左子树；如果是1，去右子树；如果都不是，抛出异常。当遍历结点走到了叶子节点时，将当前字符添加至结果，并从树的根结点开始遍历，直到将输入的字符串遍历完。

其中，遇到的坑是判断的逻辑，应该是先往左或右去走，再判断是不是叶子结点，而不是先判断再走。原因是在此处，默认至少树中是有2个以上的结点的，因为如果只有头结点一个叶子结点，是无法编码的，也就无法解码。因此头结点是不用判断的，当到了头结点，至少要先走出一步再进行判断，不然会少判断一个字符，造成解码错误。基本原理是1或者0的状态，是在在路径上的结点才有的，也就是要先走一步才有1或者0的状态，因此要先走一步，再进行判断。

第二个坑是char字符的判断，字符用单引号，字符串用双引号，因为刚开始的时候比较的为(0or1)，比较的不是0与1字符，因此一直判断不对 。总的代码如下

//译码
   public String decodeHaff(String str, HaffNode head){
       if (head == null)
           return null;                                                                               
       //返回结果
       StringBuilder res = new StringBuilder();
       HaffNode cur = head;
       for (int i = 0; i < str.length(); i++) {
           //如果当前为0，往左走，如果为1，往右走
           Character nowChar = str.charAt(i);
           //字符使用单引号，字符串使用双引号
           //是0往左走，是1往右走
           if (nowChar.equals('0')) {
               cur = cur.left;
           } else if (nowChar.equals('1')) {
               cur = cur.right;
           } else {
               throw new RuntimeException("译码错误");
           }
           //如果当前节点为叶节点，添加至结果，再从头开始找
           if (cur.left == null && cur.right == null) {
               res.append(cur.c);
               cur = head;
           }
       }
       return res.toString();
   }

构造总方法

因此总的方法为：如果传入的是字符串，使用无参的得到频率方法；若传入的是数组，使用有参的得到频率方法，然后后面的均为构造树，返回类型为得到的字符与二进制编码的Map，具体代码如下：

  //主方法，对应输入string的构造方法
  public Map mainHaff(){
      System.out.println("所有字母及频数如下");
      //1、得到每个字符的频率并放入堆中
      getFre();
      return getTree();
  }
  //主方法，对应输入字母，频数的输入方式
  public Map mainHaff(int[] arr){
      //从桶中取出来数，统计每个字母的个数
      getFre(arr);
      return getTree();
  }
//已经得到了堆，用堆得到哈夫曼树
  public Map getTree(){
      //1、构建哈夫曼树
      HaffNode head = getHaffTree();
      //2、看哈夫曼树的遍历
      printTree(head);
      //3、得到 每个字符的编码map
      Map map = new HashMap<>();
      String sb = new String();
      StringBuilder sum = new StringBuilder();
      encodingHaff(map,sb,sum, 0, head);
      //4、遍历map看结果
      itraMap2(map);
      //5、输出路径长度与带权值路径长度
      System.out.println("哈夫曼带权路径长度为："+sum);
      System.out.println("哈夫曼总路径长度为："+head.fre);
      return map;
  }

构造输入

输入的逻辑为：如果输入1，输入一串字符串，然后构建哈夫曼树；如果输入2，循环输入字符与频率，如果输出end表示结束，将获得的频率数组传入用于构建哈夫曼树。这样便得到了编码信息。这时候用户可以选择是否继续，如果输入1便继续，输入当前规则下得到的编码字符串，则输出为译码后的字符信息。输入代码如下

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    //提示以字符串输入还是每个字母频率
    System.out.println("请输入数字1或者2");
    System.out.println("输入1：将整个字符串输入");
    System.out.println("输入2：将字符对应的频数输入");
    int n = Integer.valueOf(bf.readLine());
    MyHaffman mf = null;
    Map map = null;
    //处理输入
    switch (n){
        case 1:
            System.out.println("请输入完整字符串");
            String str = bf.readLine().toUpperCase();
            mf = new MyHaffman(str);
            map = mf.mainHaff();
            break;
        case 2:
            System.out.println("请输入字母和频数，中间用空格隔开");
            System.out.println("以end作为结束");
            String s;
            mf = new MyHaffman();
            int[] arr = new int[26];
            while (!(s=bf.readLine()).equals("end")){
                String[] strArr = s.split(" ");
                char c = strArr[0].toUpperCase().charAt(0);
                int fre = Integer.valueOf(strArr[1]);
                mf.addCharAndFre(arr,c,fre);
            }
            map = mf.mainHaff(arr);
            break;
    }
    System.out.println("是否要继续：如果要编码，输入1；如果要译码，输入2，否则输入3");
    int opt;
    while ((opt = Integer.valueOf(bf.readLine())) != 3){
        if (opt == 1){
            System.out.println("输入要编码的字符串，如ABSFSDF");
            String str = bf.readLine().toUpperCase();
            System.out.println("编码后的二进制码为："+mf.codeHaff(str,map));
        }else if(opt == 2){
            System.out.println("输入要译码的二进制码，由0或者1组成");
            String str = bf.readLine();
            System.out.println(str);
            System.out.println("解码后的字符串为："+mf.decodeHaff(str,mf.getHaffTree()));
        }
        System.out.println("是否要继续：如果要编码，输入1；如果要译码，输入2，否则输入3");
    }
}

效果演示

输入字符串

输入字符串ABCACCDAEAE，交互过程如下

得到的所有字母及频数如下

得到的每个字符的编码规则及带权路径等如下

接着编码、解码及退出如下

可以看到正常的完成了需要的功能。

输入字符及频数

不忘初心，牢记使命。

这个博客开始的地方就是这道错题，请这位选手回到讲台。

我们开始用程序来做这一道题

交互方式如下

那么结果应该为！

所以答案选A！

小彩蛋

输入字符及频数

a 1
b 1
h 1
e 1
i 2
j 1
o 1
u 2
y 1

二进制码

01110101011111101001100000011110101

答案在文章最后

输入字符及频数

a 1
e 2
f 3
h 2
i 1
j 1
n 2
p 2
s 1
v 1
y 1

二进制码

111111111011101010010010100111011100001000111000000001101

写在最后

从不太了解哈夫曼树，到查阅博客，自己编写哈夫曼树的类，遇到问题，在leetcode和左神算法笔记中寻找方法，不断调试，踩坑，添加功能，到最后马马虎虎完成了自己要求的功能，也许其中还有很多考虑的不够周到的地方，但因为自己的好奇心去实现一个功能，确实是一件很有意思的事情。

彩蛋

彩蛋1：

字符编码

A:000 
B:010 
U:101 
E:1111 
H:011 
Y:001 
I:110 
J:100 
O:1110

二进制码

01110101011111101001100000011110101

答案：

HUBEIJIAYOU

彩蛋2：

字符编码

P:000 
A:1100 
S:1001 
E:010 
V:1010 
F:111 
H:001 
I:1000 
Y:1101 
J:1011 
N:011

对应的二进制码

111111111011101010010010100111011100001000111000000001101

答案：

FFFNVSHENJIEHAPPY