介紹

哈夫曼樹（又稱最優(yōu)樹），是一類帶權(quán)路徑長(zhǎng)度最短的樹。

路徑：從樹中的一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑
路勁的長(zhǎng)度：路勁上的分支數(shù)目稱作路徑的長(zhǎng)度
樹的路勁長(zhǎng)度：從樹根都每一結(jié)點(diǎn)的路徑長(zhǎng)度之和

帶權(quán)路徑的計(jì)算

不同帶權(quán)路徑長(zhǎng)度的二叉樹.png

哈夫曼樹的構(gòu)造方法

哈夫曼樹的構(gòu)造是有一定的規(guī)律的，我們可以總結(jié)為以下幾個(gè)步驟

1. 對(duì)結(jié)點(diǎn)進(jìn)行排序
2. 取出權(quán)值最小的兩個(gè)結(jié)點(diǎn)（A、B），構(gòu)造一個(gè)新的結(jié)點(diǎn)，且該新結(jié)點(diǎn)權(quán)值為A跟B權(quán)值之和
3. 將 2 步驟中的A、B結(jié)點(diǎn)刪除，同時(shí)將新生成的結(jié)點(diǎn)加入到樹中
4. 重復(fù) 2、3 步驟，最后就可以得到哈夫曼樹

圖例演示哈夫曼樹的生成

我們要將權(quán)值為3，7，8，29，5，11，23，14的元素組成哈夫曼樹

1. 排序得 3，5，7，8，11，14，23，29
   取出 3，5 兩個(gè)數(shù)組成新結(jié)點(diǎn)
   
   構(gòu)造1.png

2. 將得到的新結(jié)點(diǎn)從新參與排序

   
   
   構(gòu)造2.png
   
   

   繼續(xù)取出最小兩個(gè)數(shù)構(gòu)建新結(jié)點(diǎn)

   
   
   構(gòu)造3.png
3. 這時(shí)候我們繼續(xù)排序結(jié)點(diǎn)（我們會(huì)發(fā)現(xiàn)新生成的結(jié)點(diǎn)不屬于最小的兩個(gè)結(jié)點(diǎn)之一）
   
   構(gòu)造4.png
   
   但這不妨礙我們的操作，繼續(xù)生成新的結(jié)點(diǎn)
   
   構(gòu)造5.png
   
   依照以上的步驟循環(huán)到最后
   
   構(gòu)造6.png
   
   
   構(gòu)造7.png
   
   
   構(gòu)造8.png
   
   
   構(gòu)造9.png
   
   
   構(gòu)造10.png

Java代碼實(shí)現(xiàn)

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

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

// 結(jié)點(diǎn)結(jié)構(gòu)
class Node{
    // 權(quán)值
    int value;
    // 左結(jié)點(diǎn)
    Node leftChild;
    // 右結(jié)點(diǎn)
    Node rightChild;

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

// 哈弗曼樹
public class HuffmanTree {

    /**
     * 創(chuàng)建哈弗曼樹
     * @param arr
     * @return
     */
    public static Node createHuffmanTree(int arr[]){
        // 將傳進(jìn)來(lái)的數(shù)組元素創(chuàng)建成結(jié)點(diǎn)
        List<Node> nodes = new ArrayList<>();
        for (int value: arr){
            nodes.add(new Node(value));
        }
        // 循環(huán)處理以下操作
        while (nodes.size()>1){
            // 依據(jù)權(quán)值排序（選擇排序算法）
            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);
            }
            // 取出權(quán)值最小的兩個(gè)二叉樹
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            // 創(chuàng)建新的二叉樹
            Node parent = new Node(leftNode.value+rightNode.value);
            // 移除取出的二叉樹
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 放入原來(lái)的二叉樹集合中
            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);
    }
}

運(yùn)行結(jié)果