Java數據結構之實現哈夫曼樹的示例分析

這篇文章主要介紹了Java數據結構之實現哈夫曼樹的示例分析，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

一、與哈夫曼樹相關的概念

二、什么是哈夫曼樹

定義:

• 給定n個權值作為n個葉子結點, 構造出的一棵帶權路徑長度(WPL)最短的二叉樹,叫哈夫曼樹(), 也被稱為最最優二叉樹.

• WPL: Weighted Path Length of Tree 樹的帶權路徑長度

哈夫曼樹的特點:

1.權值越大的結點, 距離根節點越近;

2.樹中沒有度為1的結點, 哈夫曼樹的度只能是0 或 1;

3.帶權路徑長度最短的一棵二叉樹;

判斷下圖三個二叉樹那個是哈夫曼樹?

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

那么我們是如何手動構造出一棵哈夫曼樹的呢?

三、哈夫曼樹的構造方法

構造哈夫曼樹的步驟:

1.把所有結點的權值按照從小到大的順序進行排序;

2.取出根節點權值最小的兩棵二叉樹;

3.組成一棵新的二叉樹, 這課新二叉樹的根節點的權值是前面兩棵二叉樹權值的和

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

[圖解分析構造過程]

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

首先對序列進行升序排列,得到{3,7,8,13};

取出權值最小的兩個結點3,7 , 組成一棵二叉樹,根節點是權值為10的結點;

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

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

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

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

四、哈夫曼樹的代碼實現

結點類

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();
    }

    // 設置左右子節點
    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+"}";
    }
    //根據權值對結點進行排序
//    public int compareTo(Object obj){
//        return this.weight - ((HTreeNode)(obj)).weight;
//    }
    public int compareTo(HTreeNode node){
        return this.weight - node.weight;
    }
}

哈夫曼樹類

package DataStrcture.huffmantreedemo;

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

public class HuffmanTree{
    //哈夫曼樹的實現:
    //1. 構建哈夫曼樹的方法 buildHuffumanTree(int[] arr)
    //2. 對哈夫曼樹進行遍歷(二叉樹遍歷)
    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. 把存放權值的數組拿出來構建結點
        //2. 把這些節點存放到集合中
        for(int x : arr){
            nodesList.add(new HTreeNode(x));
        }
        while(nodesList.size() > 1){
            //3. 利用集合的排序方法,可以根據權值對結點進行排序
            Collections.sort(nodesList);
            // (當然了, 我們需要實現comparable接口中的copareTo方法), 在哪實現的? 在結點類中!
            //4. 不斷的循環從集合中取出兩個結點進行相加, 直到集合中只剩下一個結點才會終止循環
            HTreeNode leftNode = nodesList.get(0);
            HTreeNode rightNode = nodesList.get(1);

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

Java可以用來干什么

Java主要應用于：1. web開發；2. Android開發；3. 客戶端開發；4. 網頁開發；5. 企業級應用開發；6. Java大數據開發；7.游戲開發等。

感謝你能夠認真閱讀完這篇文章，希望小編分享的“Java數據結構之實現哈夫曼樹的示例分析”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!