哈夫曼树

定义

给定n个权值作为n个叶子结点，构造一颗二叉树，若该树的带权路径长度（wpl）达到最小，称这样的二叉树位最优二叉树，也称哈夫曼树(Huffman Tree)。
哈夫曼树是带权路径长度最短的树，权值较大的结点离跟较近
路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根节点的层数为1，则从根结点到第L层结点的路径长度为L-1
结点的权及带权路径长度：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

以下图为例，来解释WPL与哈夫曼树的关系。

利用程序创建哈夫曼树的步骤：
实例：给数列{13，7，8，3，29，6，1}，要求转成一颗哈夫曼树
步骤：
1、从大到小进行排序，将每一个数据，每一个数据都是一个结点，每个结点可以看成是一颗最简单的二叉树
2、取出根结点权值最小的两颗二叉树
3、组成一颗新的二叉树，该新的二叉树的根结点的权值是前面两颗二叉树根结点权值的和
4、再将这颗新的二叉树，以根结点的权值大小再次排序，不断重复1-2-3-4步骤，直到数列中所有数都被处理，就得到一颗哈夫曼树，如图。

代码实现

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


public class HuffmanTree {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[]= {13,7,8,3,29,6,1};
        Node root=createHuffmanTree(arr);

        //测试结果
        preOrder(root);
    }

    //编写一个前序遍历的方法
    public static void preOrder(Node root) {
        if(root!=null) {
            root.PreOrder();
        }else {
            System.out.println("空树，不能遍历！！！");
        }
    }    
    //创建哈夫曼树的方法
    public static Node createHuffmanTree(int[] arr) {
        //第一步为了操作方便
        //先遍历arr数组，将arr的每个元素构成一个Node结点
        //将Node结点放入ArrayList中
        List<Node> nodes=new ArrayList<Node>();
        for(int value:arr) {
            nodes.add(new Node(value));
        }

        //处理的过程是一个循环的过程
        while(nodes.size()>1) {
            //排序，从小到大
            Collections.sort(nodes);

            System.out.println("nodes="+nodes);

            //取出根结点权值最小的两颗二叉树
            //先取权值最小的结点二叉树
            Node leftNode=nodes.get(0);
            //再取权值第二小的结点二叉树
            Node rightNode=nodes.get(1);

            //构建新的一颗二叉树
            Node parent=new Node(leftNode.value+rightNode.value);
            parent.left=leftNode;
            parent.right=rightNode;

            //从ArrayList删除处理过的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            //将parent结点加入nodes
            nodes.add(parent);
        }

        //返回哈夫曼树的根结点
        return nodes.get(0);
    }

}

//创建结点类
//为了让Node对象持续排序Collections集合排序
//让Node实现Comparable接口
class Node implements Comparable<Node>{

    int value;            //结点权值
    Node left;
    Node right;

    //写前序遍历
    public void PreOrder() {
        System.out.println(this);
        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) {
        // TODO Auto-generated method stub
        return this.value-o.value;              //注意此处的改动，是为了让nodes权值从小到大排序
    }


}