[[389315]]

基本介紹

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

赫夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的節(jié)點離根很近。

幾個重要概念

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

wpl=59的是赫夫曼樹

赫夫曼樹創(chuàng)建思路

給定一個數(shù)列{13,7,8,3,29,6,1}，要求轉(zhuǎn)成一個赫夫曼樹

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

代碼案例

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} 
         */ 
    } 
 
    //創(chuàng)建赫夫曼樹 
    public static Node createHuffmanTree(int[] arr) { 
        //第一步為了操作方便 
        //1.遍歷 arr 數(shù)組 
        //2.將 arr 的每個元素構(gòu)成一個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); 
 
            //取出根節(jié)點權(quán)值最小的兩顆二叉樹 
            //(1)取出權(quán)值最小的節(jié)點(二叉樹) 
            Node leftNode = nodes.get(0); 
            //(2) 取出權(quán)值第二小的節(jié)點(二叉樹) 
            Node rightNode = nodes.get(1); 
 
            //(3) 構(gòu)建一顆新的二叉樹 
            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節(jié)點 
        return nodes.get(0); 
 
    } 
 
    public static void preOrder(Node node) { 
        if (node != null) { 
            node.preOrder(); 
        } else { 
            System.out.println("是空樹，不能遍歷~~"); 
        } 
 
    } 
} 
 
//創(chuàng)建節(jié)點類,為了讓Node對象支持排序，實現(xiàn)了Comparble接口 
class Node implements Comparable<Node> { 
    //權(quán)值 
    int value; 
    //指向左子節(jié)點 
    Node left; 
    //指向右子節(jié)點 
    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; 
    } 
} 

 【編輯推薦】