本篇內(nèi)容介紹了“如何使用Java赫夫曼樹技術(shù)”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),肅州企業(yè)網(wǎng)站建設(shè),肅州品牌網(wǎng)站建設(shè),網(wǎng)站定制,肅州網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,肅州網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

基本介紹

給定 n 個(gè)權(quán)值作為 n 個(gè)葉子節(jié)點(diǎn)，構(gòu)造一顆二叉樹，若該樹的帶權(quán)路徑長(zhǎng)度(wpl)達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也成為哈夫曼樹(Huffman  Tree)，還有的書翻譯成霍夫曼樹。

赫夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，權(quán)值較大的節(jié)點(diǎn)離根很近。

幾個(gè)重要概念

1. **路徑和路徑長(zhǎng)度：**在一顆樹種，從一個(gè)節(jié)點(diǎn)往下可以達(dá)到的孩子或?qū)O子節(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則從根節(jié)點(diǎn)到L層節(jié)點(diǎn)的路徑長(zhǎng)度為：L-1.

2. **節(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度：**若將樹種的節(jié)點(diǎn)賦給一個(gè)有某種含義的數(shù)值，則這個(gè)數(shù)值稱為該節(jié)點(diǎn)的權(quán)。節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根節(jié)點(diǎn)到該節(jié)點(diǎn)之間的路徑長(zhǎng)度與該節(jié)點(diǎn)的權(quán)的乘積。

3. 樹的帶權(quán)路徑長(zhǎng)度：樹的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，即為WPL(weighted path  length)，權(quán)值越大的節(jié)點(diǎn)離根節(jié)點(diǎn)越近的二叉樹才是最優(yōu)二叉樹。

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

wpl=59的是赫夫曼樹

赫夫曼樹創(chuàng)建思路

給定一個(gè)數(shù)列{13,7,8,3,29,6,1}，要求轉(zhuǎn)成一個(gè)赫夫曼樹

1. 從小到大進(jìn)行排序，將每一個(gè)數(shù)據(jù)都看成一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以看成是一顆最簡(jiǎn)單的二叉樹。

2. 取出根節(jié)點(diǎn)權(quán)值最小的兩顆二叉樹。

3. 組成一顆新的二叉樹，該新的二叉樹的根節(jié)點(diǎn)的權(quán)值就是前面兩個(gè)二叉樹根節(jié)點(diǎn)權(quán)值的和。

4. 再將這個(gè)新的二叉樹，以根節(jié)點(diǎn)的權(quán)值大小排次排序，不斷重復(fù)1-2-3-4的步驟，直到數(shù)列中，所有的數(shù)據(jù)都被處理，就得到一顆赫夫曼樹。如下圖所示：

代碼案例

package com.xie.huffmantree;  import java.util.ArrayList; import java.util.Collections; import java.util.List;  public class HuffmanTree {     public static void main(String[] args) {         int[] arr = {13, 7, 8, 3, 29, 6, 1};         Node huffmanTree = createHuffmanTree(arr);         //前序遍歷         preOrder(huffmanTree);         /**          * Node{value=67}          * Node{value=29}          * Node{value=38}          * Node{value=15}          * Node{value=7}          * Node{value=8}          * Node{value=23}          * Node{value=10}          * Node{value=4}          * Node{value=1}          * Node{value=3}          * Node{value=6}          * Node{value=13}          */     }      //創(chuàng)建赫夫曼樹     public static Node createHuffmanTree(int[] arr) {         //第一步為了操作方便         //1.遍歷 arr 數(shù)組         //2.將 arr 的每個(gè)元素構(gòu)成一個(gè)Node         //3.將 Node 放入 ArrayList中         List nodes = new ArrayList<>();         for (int value : arr) {             nodes.add(new Node(value));         }          while (nodes.size() > 1) {             //排序 從小到大             Collections.sort(nodes);             System.out.println("nodes = " + nodes);              //取出根節(jié)點(diǎn)權(quán)值最小的兩顆二叉樹             //(1)取出權(quán)值最小的節(jié)點(diǎn)(二叉樹)             Node leftNode = nodes.get(0);             //(2) 取出權(quán)值第二小的節(jié)點(diǎn)(二叉樹)             Node rightNode = nodes.get(1);              //(3) 構(gòu)建一顆新的二叉樹             Node parent = new Node(leftNode.value + rightNode.value);             parent.left = leftNode;             parent.roght = rightNode;              //(4) 從ArrayList中刪除處理過的二叉樹             nodes.remove(leftNode);             nodes.remove(rightNode);              //(5) 將parent加入nodes             nodes.add(parent);         }          //返回赫夫曼樹的root節(jié)點(diǎn)         return nodes.get(0);      }      public static void preOrder(Node node) {         if (node != null) {             node.preOrder();         } else {             System.out.println("是空樹，不能遍歷~~");         }      } }  //創(chuàng)建節(jié)點(diǎn)類,為了讓Node對(duì)象支持排序，實(shí)現(xiàn)了Comparble接口 class Node implements Comparable {     //權(quán)值     int value;     //指向左子節(jié)點(diǎn)     Node left;     //指向右子節(jié)點(diǎn)     Node roght;      //寫一個(gè)前序遍歷     public void preOrder() {         System.out.println(this);         if (this.left != null) {             this.left.preOrder();         }          if (this.roght != null) {             this.roght.preOrder();         }     }      public Node(int value) {         this.value = value;     }      @Override     public String toString() {         return "Node{" +                 "value=" + value +                 '}';     }      @Override     public int compareTo(Node o) {         //從小到大進(jìn)行排序         return this.value - o.value;     } }

“如何使用Java赫夫曼樹技術(shù)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！