介绍

哈夫曼树（又称最优树），是一类带权路径长度最短的树。

路径：从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径
路劲的长度：路劲上的分支数目称作路径的长度
树的路劲长度：从树根都每一结点的路径长度之和

带权路径的计算

不同带权路径长度的二叉树.png
从以上的图我们可以看出第三个二叉树WPL（带权路径长度）最小，而且其也是最优二叉树

哈夫曼树的构造方法

哈夫曼树的构造是有一定的规律的，我们可以总结为以下几个步骤

1. 对结点进行排序
2. 取出权值最小的两个结点（A、B），构造一个新的结点，且该新结点权值为A跟B权值之和
3. 将 2 步骤中的A、B结点删除，同时将新生成的结点加入到树中
4. 重复 2、3 步骤，最后就可以得到哈夫曼树

图例演示哈夫曼树的生成

我们要将权值为3，7，8，29，5，11，23，14的元素组成哈夫曼树

1. 排序得 3，5，7，8，11，14，23，29
   取出 3，5 两个数组成新结点
   构造1.png

2. 将得到的新结点从新参与排序

   
   构造2.png
   

   继续取出最小两个数构建新结点

   
   构造3.png
3. 这时候我们继续排序结点（我们会发现新生成的结点不属于最小的两个结点之一）
   构造4.png
   但这不妨碍我们的操作，继续生成新的结点
   构造5.png
   依照以上的步骤循环到最后
   构造6.png
   构造7.png
   构造8.png
   构造9.png
   构造10.png

Java代码实现

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

/**
 * 哈夫曼树
 * Created by Sheldon on 2019/4/11.
 * Project Name: alstudy.
 * Package Name: tree.
 */

// 结点结构
class Node{
    // 权值
    int value;
    // 左结点
    Node leftChild;
    // 右结点
    Node rightChild;

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

// 哈弗曼树
public class HuffmanTree {

    /**
     * 创建哈弗曼树
     * @param arr
     * @return
     */
    public static Node createHuffmanTree(int arr[]){
        // 将传进来的数组元素创建成结点
        List<Node> nodes = new ArrayList<>();
        for (int value: arr){
            nodes.add(new Node(value));
        }
        // 循环处理以下操作
        while (nodes.size()>1){
            // 依据权值排序（选择排序算法）
            Node temp;
            for (int i=0; i<nodes.size(); i++){
                int k = i;
                for (int j=nodes.size()-1; j>i; j--){
                    if (nodes.get(j).value < nodes.get(k).value){
                        k = j;
                    }
                }
                temp = nodes.get(i);
                nodes.set(i, nodes.get(k));
                nodes.set(k, temp);
            }
            // 取出权值最小的两个二叉树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            // 创建新的二叉树
            Node parent = new Node(leftNode.value+rightNode.value);
            // 移除取出的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 放入原来的二叉树集合中
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    public static void main(String[] args) {
        int[] arr = {3,7,8,29,5,11,23,14};
        Node root = HuffmanTree.createHuffmanTree(arr);
        System.out.println(root.value);
    }
}

运行结果