如何使用Java赫夫曼樹技術(shù)

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

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

如何使用Java赫夫曼樹技術(shù)

基本介紹

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

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

幾個重要概念

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

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

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

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

如何使用Java赫夫曼樹技術(shù)

wpl=59的是赫夫曼樹

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

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

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

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

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

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

如何使用Java赫夫曼樹技術(shù)

代碼案例

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òu)成一個Node         //3.將 Node 放入 ArrayList中         List<Node> 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é)點權(quán)值最小的兩顆二叉樹             //(1)取出權(quán)值最小的節(jié)點(二叉樹)             Node leftNode = nodes.get(0);             //(2) 取出權(quán)值第二小的節(jié)點(二叉樹)             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é)點         return nodes.get(0);      }      public static void preOrder(Node node) {         if (node != null) {             node.preOrder();         } else {             System.out.println("是空樹，不能遍歷~~");         }      } }  //創(chuàng)建節(jié)點類,為了讓Node對象支持排序，實現(xiàn)了Comparble接口 class Node implements Comparable<Node> {     //權(quán)值     int value;     //指向左子節(jié)點     Node left;     //指向右子節(jié)點     Node roght;      //寫一個前序遍歷     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) {         //從小到大進行排序         return this.value - o.value;     } }

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

本文題目：如何使用Java赫夫曼樹技術(shù)
文章來源：http://muchs.cn/article24/ipjsje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、網(wǎng)站設(shè)計公司、移動網(wǎng)站建設(shè)、小程序開發(fā)、面包屑導(dǎo)航、網(wǎng)頁設(shè)計公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

商城網(wǎng)站建設(shè)