什么是哈夫曼树

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

简介

在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+...+WnLn），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。

基本术语

1. 路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2. 结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
**3. ** 树的带权路径长度'

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

实现代码：

import java.util.*;

public class Huffman {

    public static void main(String[] args) {
        int[] arr = {10, 5, 1, 2, 9, 15, 6, 3, 4};
        long start = System.currentTimeMillis();
        System.out.println("没优化前：");
        TreeNode root = CreateHuffman(arr);
        System.out.println("前序遍历结果：");
        PreTraver(root);
        long end = System.currentTimeMillis();
        System.out.println("共耗时：" + (end - start) + "ms");

        System.out.println("----------------------------------");

        start = System.currentTimeMillis();
        System.out.println("优化后：");
        TreeNode rootByPQ = creatHuffmanByPriorityQueue(arr);
        System.out.println("前序遍历结果：");
        PreTraver(rootByPQ);
        end = System.currentTimeMillis();
        System.out.println("共耗时：" + (end - start) + "ms");
    }

    /**
     * 未经过优化
     * @param arr
     * @return
     */
    public static TreeNode CreateHuffman(int[] arr) {
        List<TreeNode> treeNodes = new ArrayList<TreeNode>();
        for (int i = 0; i < arr.length; i++) {
            treeNodes.add(new TreeNode(arr[i], null, null));
        }

        //如果treenodes长度为1，则哈夫曼树创建好了，只剩下根结点
        while (treeNodes.size() > 1) {

            //使用Collections集合对treenodes进行排序
            Collections.sort(treeNodes, new Comparator<TreeNode>() {
                @Override
                public int compare(TreeNode o1, TreeNode o2) {
                    return o1.getNo() - o2.getNo();
                }
            });

            //排序之后，取出头两个进行创建结点
            TreeNode left = treeNodes.get(0);
            TreeNode right = treeNodes.get(1);
            TreeNode parent = new TreeNode(left.getNo() + right.getNo(), null, null);

            //根结点创建好之后，将左右结点接上去,并将根结点加入集合
            parent.setLeft(left);
            parent.setRight(right);
            treeNodes.add(parent);

            //之后将头两个节点删除
            treeNodes.remove(left);
            treeNodes.remove(right);

        }
        return treeNodes.get(0);
    }

    /**
     * 经过优先队列优化
     * @param arr
     * @return
     */
    public static TreeNode creatHuffmanByPriorityQueue(int[] arr) {

        //构造结点依次加入优先队列
        Queue<TreeNode> pq = new PriorityQueue<TreeNode>(new Comparator<TreeNode>() {
            @Override
            public int compare(TreeNode o1, TreeNode o2) {
                return o1.getNo() - o2.getNo();
            }
        });

        for (int i = 0; i < arr.length; i++) {
            pq.offer(new TreeNode(arr[i], null, null));
        }

        //当队列中只剩一个元素时，Huffman树就创建完成了
        while(pq.size() > 1){

            //从优先队列中取出值最小的两个结点
            TreeNode left = pq.poll();
            TreeNode right = pq.poll();

            //创建父结点
            TreeNode parent = new TreeNode(left.getNo() + right.getNo(),null,null);

            //为父结点添加左右孩子
            parent.setLeft(left);
            parent.setRight(right);

            //加入优先队列
            pq.offer(parent);

        }

        return pq.poll();
    }

    public static void PreTraver(TreeNode root) {
        if (root != null) {
            System.out.print(root.getNo() + " ");
            PreTraver(root.getLeft());
            PreTraver(root.getRight());
        }
    }
}


/**
 * Huffman树的结点
 */
class TreeNode {

    private int no;             //编号
    private TreeNode left;      //左结点
    private TreeNode right;     //右节点

    public TreeNode(int no, TreeNode left, TreeNode right) {
        this.no = no;
        this.left = left;
        this.right = right;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

示例结果：

Q.E.D.