1.基本介紹

1. 給定 n 個權值作為 n 個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree), 還有的書翻譯為霍夫曼樹。

2. 赫夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近

2.赫夫曼樹幾個重要概念和舉例說明

1) 路徑和路徑長度：在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路

2) 結點的權及帶權路徑長度：若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積

3) 樹的帶權路徑長度：樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長度之和，記為 WPL(weighted path length) ,權值越大的結點離根結點越近的二叉樹才是最優(yōu)二叉樹。

WPL 最小的就是赫夫曼樹

3.構成赫夫曼樹的步驟

1. 從小到大進行排序, 將每一個數據，每個數據都是一個節(jié)點 ， 每個節(jié)點可以看成是一顆最簡單的二叉樹

2. 取出根節(jié)點權值最小的兩顆二叉樹

3. 組成一顆新的二叉樹, 該新的二叉樹的根節(jié)點的權值是前面兩顆二叉樹根節(jié)點權值的和

4. 再將這顆新的二叉樹，以根節(jié)點的權值大小 再次排序， 不斷重復1-2-3-4 的步驟，直到數列中，所有的數據都被處理，就得到一顆赫夫曼樹

赫夫曼樹

4.代碼

4.1 創(chuàng)建結點類

為了讓Node 對象持續(xù)排序Collections集合排序

讓Node 實現Comparable接口

class Node implements Comparable<Node> {
    int value; // 結點權值
    char c; //字符
    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;
    }

}

4.2 創(chuàng)建赫夫曼樹的方法

/**
     * 
     * @param arr 需要創(chuàng)建成哈夫曼樹的數組
     * @return 創(chuàng)建好后的赫夫曼樹的root結點
     */
    public static Node createHuffmanTree(int[] arr) {
        // 第一步為了操作方便
        // 1. 遍歷 arr 數組
        // 2. 將arr的每個元素構成成一個Node
        // 3. 將Node 放入到ArrayList中
        List<Node> nodes = new ArrayList<Node>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        
        //我們處理的過程是一個循環(huán)的過程
        
        
        while(nodes.size() > 1) {
        
            //排序 從小到大 
            Collections.sort(nodes);
            
            System.out.println("nodes =" + nodes);
            
            //取出根節(jié)點權值最小的兩顆二叉樹 
            //(1) 取出權值最小的結點（二叉樹）
            Node leftNode = nodes.get(0);
            //(2) 取出權值第二小的結點（二叉樹）
            Node rightNode = nodes.get(1);
            
            //(3)構建一顆新的二叉樹
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;
            
            //(4)從ArrayList刪除處理過的二叉樹
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //(5)將parent加入到nodes
            nodes.add(parent);
        }
        
        //返回哈夫曼樹的root結點
        return nodes.get(0);
        
    }

4.3 編寫一個前序遍歷的方法

public static void preOrder(Node root) {
        if(root != null) {
            root.preOrder();
        }else{
            System.out.println("是空樹，不能遍歷~~");
        }
    }

4.4 測試

public static void main(String[] args) {
        int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
        Node root = createHuffmanTree(arr);
        
        //測試一把
        preOrder(root); //
        
    }