Java數據結構之哈夫曼樹(shù)概述及實(shí)現

目錄

一、與哈夫曼樹(shù)相關(guān)的概念

二、什么是哈夫曼樹(shù)

定義:

• 給定n個(gè)權值作為n個(gè)葉子結點(diǎn), 構造出的一棵帶權路徑長(cháng)度(WPL)最短的二叉樹(shù),叫哈夫曼樹(shù)(), 也被稱(chēng)為最最優(yōu)二叉樹(shù).
• WPL: Weighted Path Length of Tree 樹(shù)的帶權路徑長(cháng)度

哈夫曼樹(shù)的特點(diǎn):

1.權值越大的結點(diǎn), 距離根節點(diǎn)越近;

2.樹(shù)中沒(méi)有度為1的結點(diǎn), 哈夫曼樹(shù)的度只能是0 或 1;

3.帶權路徑長(cháng)度最短的一棵二叉樹(shù);

判斷下圖三個(gè)二叉樹(shù)那個(gè)是哈夫曼樹(shù)?

• 當然是WPL最小的樹(shù)啦, 即中間的二叉樹(shù)是也;

那么我們是如何手動(dòng)構造出一棵哈夫曼樹(shù)的呢?

三、哈夫曼樹(shù)的構造方法

構造哈夫曼樹(shù)的步驟:

1.把所有結點(diǎn)的權值按照從小到大的順序進(jìn)行排序;

2.取出根節點(diǎn)權值最小的兩棵二叉樹(shù);

3.組成一棵新的二叉樹(shù), 這課新二叉樹(shù)的根節點(diǎn)的權值是前面兩棵二叉樹(shù)權值的和

4.再將這棵新的二叉樹(shù),以根節點(diǎn)的權值大小進(jìn)行排序, 不斷重復1-2-3-4的步驟, 直到給定序列中的所有權值都被處理,我們就得到了一棵哈夫曼樹(shù).

[圖解分析構造過(guò)程]

下面以序列{13,7,8,3}為例, 圖解構造哈夫曼樹(shù)的過(guò)程

首先對序列進(jìn)行升序排列,得到{3,7,8,13};

取出權值最小的兩個(gè)結點(diǎn)3,7 , 組成一棵二叉樹(shù),根節點(diǎn)是權值為10的結點(diǎn);

在原序列中去除步驟2中已經(jīng)被使用了的3和7, 并把新的結點(diǎn)權值10加入到序列中并重新排序, 得到{8,10,13};

再次取出權值最小的兩個(gè)節點(diǎn)8,10, 組成一棵根節點(diǎn)為18的二叉樹(shù), 然后我們去除序列中的8,10, 將18添加到序列中并排序, 得到了{13,18};

將序列{13,18}取出構成一棵新的二叉樹(shù), 權值為31, 此時(shí)序列中只剩下了31這個(gè)結點(diǎn), 他是這個(gè)哈夫曼樹(shù)的根節點(diǎn);

至此, {13,7,8,3}的哈夫曼樹(shù)構建完畢.

四、哈夫曼樹(shù)的代碼實(shí)現

結點(diǎn)類(lèi)

package DataStrcture.huffmantreedemo;

public class HTreeNode implements Comparable<HTreeNode>{
    //
    public HTreeNode leftNode;
    public HTreeNode rightNode;
    public int weight;

    // 前序遍歷
    public void preOrder(){

        System.out.println(this);

        if(this.leftNode != null) this.leftNode.preOrder();

        if(this.rightNode != null) this.rightNode.preOrder();
    }

    // 設置左右子節點(diǎn)
    public void setLeftNode(HTreeNode node){
        this.leftNode = node;
    }
    public void setRightNode(HTreeNode node){
        this.rightNode = node;
    }
    //構造方法和toString()
    public HTreeNode(int weight){
        this.weight = weight;
    }
    public String toString(){
        return "Node{weight: "+weight+"}";
    }
    //根據權值對結點(diǎn)進(jìn)行排序
//    public int compareTo(Object obj){
//        return this.weight - ((HTreeNode)(obj)).weight;
//    }
    public int compareTo(HTreeNode node){
        return this.weight - node.weight;
    }
}

哈夫曼樹(shù)類(lèi)

package DataStrcture.huffmantreedemo;

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

public class HuffmanTree{
    //哈夫曼樹(shù)的實(shí)現:
    //1. 構建哈夫曼樹(shù)的方法 buildHuffumanTree(int[] arr)
    //2. 對哈夫曼樹(shù)進(jìn)行遍歷(二叉樹(shù)遍歷)
    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};
        HTreeNode hTreeNode = buildHuffmanTree(arr);
        preOrder(hTreeNode);
    }
    public static HTreeNode buildHuffmanTree(int[] arr){
        //
        ArrayList<HTreeNode> nodesList = new ArrayList<HTreeNode>();
        //1. 把存放權值的數組拿出來(lái)構建結點(diǎn)
        //2. 把這些節點(diǎn)存放到集合中
        for(int x : arr){
            nodesList.add(new HTreeNode(x));
        }
        while(nodesList.size() > 1){
            //3. 利用集合的排序方法,可以根據權值對結點(diǎn)進(jìn)行排序
            Collections.sort(nodesList);
            // (當然了, 我們需要實(shí)現comparable接口中的copareTo方法), 在哪實(shí)現的? 在結點(diǎn)類(lèi)中!
            //4. 不斷的循環(huán)從集合中取出兩個(gè)結點(diǎn)進(jìn)行相加, 直到集合中只剩下一個(gè)結點(diǎn)才會(huì )終止循環(huán)
            HTreeNode leftNode = nodesList.get(0);
            HTreeNode rightNode = nodesList.get(1);

            HTreeNode parent = new HTreeNode(leftNode.weight + rightNode.weight);
            建立父節點(diǎn)和左右子節點(diǎn)的關(guān)系(千萬(wàn)不要忘了)
            //因為我們雖說(shuō)是父節點(diǎn)和左右子節點(diǎn), 還是要實(shí)實(shí)在在的于內存中體現出來(lái)的哈
            parent.setLeftNode(leftNode);
            parent.setRightNode(rightNode);
            //5.從結合中移除用過(guò)的左右子節點(diǎn), 添加父節點(diǎn)進(jìn)去
            nodesList.remove(leftNode);
            nodesList.remove(rightNode);
            nodesList.add(parent);
        }
        //6. 返回一個(gè)最終的唯一結點(diǎn)
        return nodesList.get(0);
    }
    //前序遍歷哈夫曼樹(shù)
    public static void preOrder(HTreeNode root){
        if(root != null){
            root.preOrder();
        }else{
            System.out.println("二叉樹(shù)為空! ");
        }
    }
}

到此這篇關(guān)于Java數據結構之哈夫曼樹(shù)概述及實(shí)現的文章就介紹到這了,更多相關(guān)Java哈夫曼樹(shù)內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！