Java數據結構之哈夫曼樹概述及實現

Posted on by

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

概念 含義
1. 路徑 從樹中一個結點到另一個結點的分支所構成的路線
2. 路徑長度 路徑上的分支數目
3. 樹的路徑長度 長度從根到每個結點的路徑長度之和
4. 帶權路徑長度 結點具有權值, 從該結點到根之間的路徑長度乘以結點的權值, 就是該結點的帶權路徑長度
5. 樹的帶權路徑長度 樹中所有葉子結點的帶權路徑長度之和

二、什麼是哈夫曼樹

定義:

  • 給定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哈夫曼樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：