什么是赫夫曼树

所有带权节点的，带权路径和，最小的二叉树，称为赫夫曼树。

---

手写3,2,1,5,7,13,8的这些权重为一个赫夫曼树

1. 步骤一：将上述排序3,2,1,5,7,13,8。 为：1,2,3,5,7,8,13

2. 步骤二：取出较小的两个12 组成以及他们的和3组成一个树(小左大右)。为：

   
   image.png
3. 步骤三：将算出来的，再放入并去除12，再次排序。为3,3,5,7,8,13

4. 步骤四：再次取出较小的两个3,3 因为里面的一个3个原来的1,2的和，所以将他们放到一起。为：

   
   image.png

5. 步骤四：重复步骤3。为：5,6,7,8,13。继续取出56。为：

   
   image.png
6. 步骤五：再次去除并排序。为 7,8,11,13。取出7,8

7. 步骤六：由于取出的7,8其中没有原来相加的和，所以写在另一边。

   
   image.png

8. 步骤七：再次去除并排序。为 11,15,13。取出11,15,为：

   
   image.png

9. 步骤八：再次去除并排序。为 15,26。取出15,26,为：

   
   image.png

PS：计算WPL：WPL =节点权重*距顶点的线条个数，的和

WPL = 15 * 1 + 7 * 3 + 8 * 3 + 5 * 3 + 3 * 4 + 1 * 5 + 2 * 5 = 102

---

加出来的节点有什么用？

image.png

去除相加出来的节点,存色填充后，可以发现如下两个情况

1. 任何一个字母到头结点的路径，都不会包含其他字母。(即赫夫曼树的前缀编码依据)
2. 权重越小的距离顶节点距离越小。

---

当多个权值相等的时候怎么排序和放置(2个,3个,...n个一样的情况)？

---

赫夫曼树编码

将上述图:

所有左节点的连接线编码为0，所以右节点的线编码为1：

获得字母编码表:

字母	编码
a	0
b	100
c	101
d	110
e	1110
f	11110
g	11111

上述表中

1. 权重越多，标识出现次数越多。编码位数越小
2. 任何一个编码都不会是其他编码的子串。

---

使用代码实现赫夫曼树编码和解码

import java.util.*;

/************************************* 节点Bean ***************************************/
class 赫夫曼树节点 {
    char 真实字母;
    int 到顶节点的线条个数;
    int 该赫夫曼树节点的权重;
    boolean 是字母节点_不是求和得到的虚拟节点;
    赫夫曼树节点 左节点;
    赫夫曼树节点 右节点;
    boolean 有被遍历过 = false;
}

/************************************* 赫夫曼树 ***************************************/
public class 赫夫曼树 {
    private 赫夫曼树节点 跟节点;
    Map<Character, String> 赫夫曼树字符编码对应表 = new HashMap();
    Map<String, Character> 赫夫曼树编码字符对应表 = new HashMap();

    public Map<Character, Integer> 解析字符串_并且_返回每个字符的_权重对应关系(String 被编码字符串) {
        Map<Character, Integer> 权重对应表 = new HashMap();
        char 被编码字符串字符数组[] = 被编码字符串.toCharArray();
        Integer n;
        for (int 被编码字符串第i个字符_下标 = 0; 被编码字符串第i个字符_下标 < 被编码字符串字符数组.length; 被编码字符串第i个字符_下标++) {
            char 被编码字符串_第i个字符 = 被编码字符串字符数组[被编码字符串第i个字符_下标];
            if ((n = 权重对应表.get(被编码字符串_第i个字符)) != null) {
                权重对应表.put(被编码字符串_第i个字符, ++n);
            } else {
                权重对应表.put(被编码字符串_第i个字符, 1);
            }
        }
        return 权重对应表;
    }

    public void 根据上面返回的_权重对应表_生成赫夫曼树(Map<Character, Integer> 权重对应表) {
        if (权重对应表 == null) {
            return;
        }
        Set<Character> 权重对应表中的字母集 = 权重对应表.keySet();
        Collection<Integer> 权重对应表中的权重集 = 权重对应表.values();

        赫夫曼树节点 新的赫夫曼树左节点 = new 赫夫曼树节点(); //较小的那个
        赫夫曼树节点 新的赫夫曼树节点右节点 = new 赫夫曼树节点();
        赫夫曼树节点 新的赫夫曼树节点求和父节点 = new 赫夫曼树节点();
        新的赫夫曼树节点求和父节点.左节点 = 新的赫夫曼树左节点;
        新的赫夫曼树节点求和父节点.右节点 = 新的赫夫曼树节点右节点;
        新的赫夫曼树节点求和父节点.该赫夫曼树节点的权重 = 新的赫夫曼树节点求和父节点.左节点.该赫夫曼树节点的权重 + 新的赫夫曼树节点求和父节点.右节点.该赫夫曼树节点的权重;
    }

    private Stack<String> 编码01节点栈 = new Stack<>();

    public void 遍历赫夫曼树_并_设置字符编码和编码字符Hash表() {
        if (跟节点 == null) {
            System.out.println("需要先调用方法：根据上面返回的_权重对应表_生成赫夫曼树()");
            return;
        }
        //TODO 初始化数据
        //...
        遍历赫夫曼树用的递归方法(跟节点);
    }

    private void 遍历赫夫曼树用的递归方法(赫夫曼树节点 当前递归到的节点) {
        当前递归到的节点.有被遍历过 = true;
        if (当前递归到的节点.是字母节点_不是求和得到的虚拟节点) {
            String 当前节点编码 = 编码01节点栈.toString().replaceAll(",| |\\]|\\[", "");
            赫夫曼树字符编码对应表.put(当前递归到的节点.真实字母, 当前节点编码);
            赫夫曼树编码字符对应表.put(当前节点编码, 当前递归到的节点.真实字母);
        } else { //是虚拟节点
            if (当前递归到的节点.左节点 != null && !当前递归到的节点.左节点.有被遍历过) {
                编码01节点栈.push("0");//往左节点走,就push一个0编码
                遍历赫夫曼树用的递归方法(当前递归到的节点.左节点);
            }

            if (当前递归到的节点.右节点 != null && !当前递归到的节点.右节点.有被遍历过) {
                编码01节点栈.push("1");//往右节点走,就push一个1编码
                遍历赫夫曼树用的递归方法(当前递归到的节点.右节点);
            }
        }
        //真实节点或虚拟节点的左右子树都遍历过了,弹出最后一个编码记录
        编码01节点栈.pop();
    }

    /*********************************** 编码&译码 ***********************************/
    public String 编码(String 被编码字符串) {
        StringBuilder 编码结果字符串 = new StringBuilder();
        for (int 被编码字符串第i个字符 = 0; 被编码字符串第i个字符 < 被编码字符串.length(); 被编码字符串第i个字符++) {
            if (赫夫曼树字符编码对应表.containsKey(被编码字符串.charAt(被编码字符串第i个字符))) {
                编码结果字符串.append(赫夫曼树编码字符对应表.get(被编码字符串.charAt(被编码字符串第i个字符)));
            } else {
                throw new RuntimeException("赫夫曼树编码字符对应表中,没有对应编码:" + 被编码字符串.charAt(被编码字符串第i个字符), null);
            }
        }
        return 编码结果字符串.toString();
    }

    public String 译码(String 编码后的字符串) {
        StringBuilder 译码结果字符串 = new StringBuilder();
        StringBuilder 当前发现的编码 = new StringBuilder();
        for (int 编码后的字符串第i个字符 = 0; 编码后的字符串第i个字符 < 编码后的字符串.length(); 编码后的字符串第i个字符++) {
            当前发现的编码.append(编码后的字符串.charAt(编码后的字符串第i个字符));
            if (赫夫曼树编码字符对应表.containsKey(当前发现的编码.toString())) {
                译码结果字符串.append(赫夫曼树编码字符对应表.get(当前发现的编码.toString()));
                当前发现的编码.delete(0, 当前发现的编码.length());
            }
        }
        return 译码结果字符串.toString();
    }

}


class 测试 {
    public static void main(String[] args) {
        赫夫曼树 测试赫夫曼树 = new 赫夫曼树();
        String 测试字符串 = "afafdsfsfd";

        Map<Character, Integer> 权重对应关系 = 测试赫夫曼树.解析字符串_并且_返回每个字符的_权重对应关系(测试字符串);
        System.out.println("权重对应关系:" + 权重对应关系);
        测试赫夫曼树.根据上面返回的_权重对应表_生成赫夫曼树(权重对应关系);
        测试赫夫曼树.遍历赫夫曼树_并_设置字符编码和编码字符Hash表();
        System.out.println("赫夫曼树字符编码对应表:" + 测试赫夫曼树.赫夫曼树字符编码对应表);
        System.out.println("赫夫曼树编码字符对应表:" + 测试赫夫曼树.赫夫曼树编码字符对应表);
        String 编码后的字符串 = 测试赫夫曼树.编码(测试字符串);
        测试赫夫曼树.译码(编码后的字符串);
    }
}