資料結構之赫夫曼樹

1.赫夫曼樹基本介紹

(1)給定n個權值作為n個葉子結點,構造一顆二叉樹,若該樹的帶權路徑長度(wpl)達到最小,稱這樣的二叉樹為最優二叉樹,也稱為哈夫曼樹(HuffmanTree)

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

概念介紹

(1)路徑和路徑長度:在一棵樹中,從一個結點往下可以達到的孩子或者孫子結點之間的通路,稱為路徑,若規定根節點的層數為1,則從根節點到第L層的路徑長度為L-1

(2)結點的權及帶權路徑長度:若将樹中結點指派給一個有着某種含義的數值,則這個數值稱為該結點的權,結點的帶權路徑長度為:從根結點到該結點之間的路徑長度與該結點的權的乘積

(3)樹的帶權路徑長度:樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和,記為WPL(weighted path length),權值越大的結點離根結點越近的二叉樹是最優二叉樹

(4)WPL最小的就是赫夫曼樹.

下圖是不同的樹,樹的帶權路徑

2.建構赫夫曼樹步驟

(1)從小到大進行排序,每個資料都是一個結點,每個結點可以看成是一顆最簡單的二叉樹.

(2)取出根結點權值最小的兩顆二叉樹

(3)組成一顆新的二叉樹,該新的二叉樹的根結點的權值是前面兩顆二叉樹根結點的權值之和

(4)再将這顆新的二叉樹,以根結點的權值大小再次排序,不斷重讀1,2,3,4步驟,直到數列中,所有的資料都被處理,就得到一顆赫夫曼樹.

圖解分析:

(1)原始數組為13,7,8,3,29,6,1

(2)

(3)

(4)

(5)

(6)

圖解分析看得明白麼?看不明白沒有關系,代碼實作一下

package com.self.dataStructure.huffmanTree;

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

public class HuffmanTreedemo {
    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};
        Node root = createHuffmanTree(arr);

        preOrderMethod(root);
    }
    //編寫一個前序周遊的方法
    public static void preOrderMethod(Node root){
        if(root != null){
            root.preOrder();
        }else {
            System.out.println("current huffmanTree is null");
        }
    }
    //建立赫夫曼樹
    public static Node createHuffmanTree(int[] arr){
        //周遊數組,将數組的每一個值建構成node,将node放入到ArrayList
        List<Node> nodes = new ArrayList<>();
        for (int node : arr) {
            nodes.add(new Node(node));
        }
        while (nodes.size() > 1) {
            //排序,将數組從小到大排序
            Collections.sort(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;
            //删除list集合中的前兩個數
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将parent添加到集合
            nodes.add(parent);
        }
        return nodes.get(0);
    }

}
class Node implements Comparable<Node>{
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
    //前序周遊
    public void preOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.preOrder();
        }
        if(this.right != null){
            this.right.preOrder();
        }
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    @Override
    public int compareTo(Node o) {
        //表示從小到大排序
        return this.value - o.value;
    }
}