创建赫夫曼树

赫夫曼树

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。

赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

赫夫曼树几个重要概念和举例说明

路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积

13节点的路径长度：3-1=2
13节点的权：13
13节点的带权路径长度：2*13=26

赫夫曼树创建思路图解

给你一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树.

构成赫夫曼树的步骤：
1.从小到大进行排序, 将每一个数据，每个数据都是一个节点
2.取出根节点权值最小的两个节点组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
3.再将这颗新的二叉树，以根节点的权值大小再次排序， 不断重复 1-2-3 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

上图就是该数列的赫夫曼树，可以看见所有的叶子节点都是数列中的值，并且该树带权路径长度(wpl)达到最小。
权值较大的结点离根较近，只有这样该节点的带权路径长度才会最小，权值越大，对该树带权路径长度影响越大，所以优先考虑让权值大的节点靠根最近。

public class HaffmanTree {

    public static void main(String[] args) {
        HaffmanTree haffmanTree = new HaffmanTree();
        haffmanTree.createHaffmanTree(new int[]{13, 7, 8, 3, 29, 6, 1}).preOrder();
    }

    public Node createHaffmanTree(int[] arr) {

        List<Node> list = new ArrayList<>();
        for (int i : arr) {
            list.add(new Node(i));
        }

        while (list.size() > 1) {
            Collections.sort(list);
            Node left = list.get(0);
            Node right = list.get(1);
            Node parent = new Node(left.value + right.value);
            parent.left = left;
            parent.right = right;
            list.remove(left);
            list.remove(right);
            list.add(parent);
        }
        return list.get(0);
    }

    public void preOrder(Node node) {
        if (node == null) {
            System.out.println("当前树为空！");
            return;
        } else {
            node.preOrder();
        }
    }
}

class Node implements Comparable<Node> {

    public int value;
    public Node left;
    public Node right;


    public void preOrder() {
        System.out.print(this.value + " ");
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

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

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }
}

执行结果：67 29 38 15 7 8 23 10 4 1 3 6 13