9.2.2 赫夫曼树

1. 基础概念

1)路径和路径长度：
    路径： 在一颗树中，从一个指定节点到其子节点或者孙子节点的通路称为路径。
    路径长度：通路的分支（分段）数称为路径长度
2)节点的权和带权路径长度
    节点的权：节点中含有某种含义的数值
    节点的带权路径长度：从【根节点到该节点的路径长度】与【该节点的权】的乘积
3)树的带权路径长度【WPL】
    树的所有非叶子节点的带权路径长度之和，记为WPL
4)赫夫曼树
    WPL最小的二叉树, 也称为最优二叉树。
    WPL最小的意义，权值越大的离根节点越近
5)实际意义
    比如热点数据，权值越高，离根节点越近，检索越快

2. 构建赫夫曼树（HuffmanTree）

将一个给定数组序列，够造成一棵赫夫曼树

1. 思路分析 ```

1)数组的值可以看做节点的权 2)将每一个节点看成一个树,多颗树构成森林（开始每棵树只有一个节点） 3)根据【树的根节点的权】对【森林中的树】排序 4)取出权值最小的两个树，够造一个新树 5)将新树加入到森林,将上述权值最小的两棵树移出森林 6)重复 3-4-5 只到森林中只有一颗大树（这棵大树就是赫夫曼树）

2. 代码实现
```java
import lombok.Getter;
import lombok.Setter;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 赫夫曼子树（可理解成森林中的子树，Node为树的根节点）
 */
@Setter
@Getter
class Node implements Comparable{
    // 权值
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    /**
     * 为了便于通过权值对森林中的树进行排序
     * @param o
     * @return
     */
    @Override
    public int compareTo(Object o) {
        return this.value - ((Node)o).value;
    }
}



public class HuffmanTreeTest {
    /**
     * 构建赫夫曼树
     *  返回的就是树根节点
     * @return
     */
    public static Node buildHuffmanTree(int[] arr) {

        // 构建森林
        List<Node> trees = new ArrayList<>();
        for(int v:arr) {
            Node tree = new Node(v);
            trees.add(tree);
        }

        // 目标是构建一颗树
        while(trees.size()>1) {
            // 对森林排序
            Collections.sort(trees);
            // 通过最小的两棵树构造新树
            Node min1 = trees.get(0);
            Node min2 = trees.get(1);
            Node newTree = new Node(min1.getValue() + min2.getValue());
            newTree.setLeft(min1);
            newTree.setRight(min2);
            // 将新树放入省略，将两棵小树移出
            trees.add(newTree);
            trees.remove(min1);
            trees.remove(min2);
        }
        // 返回赫夫曼树（根节点）
        return trees.get(0);
    }
}