[[389315]]

基本介紹

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

赫夫曼樹是帶權路徑長度最短的樹，權值較大的節點離根很近。

幾個重要概念

1. **路徑和路徑長度：**在一顆樹種，從一個節點往下可以達到的孩子或孫子節點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根節點的層數為1，則從根節點到L層節點的路徑長度為：L-1.
2. **節點的權和帶權路徑長度：**若將樹種的節點賦給一個有某種含義的數值，則這個數值稱為該節點的權。節點的帶權路徑長度為：從根節點到該節點之間的路徑長度與該節點的權的乘積。
3. 樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子節點的帶權路徑長度之和，即為WPL(weighted path length)，權值越大的節點離根節點越近的二叉樹才是最優二叉樹。
4. WPL最小的就是赫夫曼樹

wpl=59的是赫夫曼樹

赫夫曼樹創建思路

給定一個數列{13,7,8,3,29,6,1}，要求轉成一個赫夫曼樹

1. 從小到大進行排序，將每一個數據都看成一個節點，每個節點可以看成是一顆最簡單的二叉樹。
2. 取出根節點權值最小的兩顆二叉樹。
3. 組成一顆新的二叉樹，該新的二叉樹的根節點的權值就是前面兩個二叉樹根節點權值的和。
4. 再將這個新的二叉樹，以根節點的權值大小排次排序，不斷重復1-2-3-4的步驟，直到數列中，所有的數據都被處理，就得到一顆赫夫曼樹。如下圖所示：

代碼案例

package com.xie.huffmantree; 
 
import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 
 
public class HuffmanTree { 
    public static void main(String[] args) { 
        int[] arr = {13, 7, 8, 3, 29, 6, 1}; 
        Node huffmanTree = createHuffmanTree(arr); 
        //前序遍歷 
        preOrder(huffmanTree); 
        /** 
         * Node{value=67} 
         * Node{value=29} 
         * Node{value=38} 
         * Node{value=15} 
         * Node{value=7} 
         * Node{value=8} 
         * Node{value=23} 
         * Node{value=10} 
         * Node{value=4} 
         * Node{value=1} 
         * Node{value=3} 
         * Node{value=6} 
         * Node{value=13} 
         */ 
    } 
 
    //創建赫夫曼樹 
    public static Node createHuffmanTree(int[] arr) { 
        //第一步為了操作方便 
        //1.遍歷 arr 數組 
        //2.將 arr 的每個元素構成一個Node 
        //3.將 Node 放入 ArrayList中 
        List<Node> nodes = new ArrayList<>(); 
        for (int value : arr) { 
            nodes.add(new Node(value)); 
        } 
 
        while (nodes.size() > 1) { 
            //排序 從小到大 
            Collections.sort(nodes); 
            System.out.println("nodes = " + nodes); 
 
            //取出根節點權值最小的兩顆二叉樹 
            //(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.roght = rightNode; 
 
            //(4) 從ArrayList中刪除處理過的二叉樹 
            nodes.remove(leftNode); 
            nodes.remove(rightNode); 
 
            //(5) 將parent加入nodes 
            nodes.add(parent); 
        } 
 
        //返回赫夫曼樹的root節點 
        return nodes.get(0); 
 
    } 
 
    public static void preOrder(Node node) { 
        if (node != null) { 
            node.preOrder(); 
        } else { 
            System.out.println("是空樹，不能遍歷~~"); 
        } 
 
    } 
} 
 
//創建節點類,為了讓Node對象支持排序，實現了Comparble接口 
class Node implements Comparable<Node> { 
    //權值 
    int value; 
    //指向左子節點 
    Node left; 
    //指向右子節點 
    Node roght; 
 
    //寫一個前序遍歷 
    public void preOrder() { 
        System.out.println(this); 
        if (this.left != null) { 
            this.left.preOrder(); 
        } 
 
        if (this.roght != null) { 
            this.roght.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; 
    } 
} 

 【編輯推薦】