您好,登錄后才能下訂單哦!
這篇文章主要介紹了Java數(shù)據(jù)結構之實現(xiàn)哈夫曼樹的示例分析,具有一定借鑒價值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
概念 | 含義 |
1. 路徑 | 從樹中一個結點到另一個結點的分支所構成的路線 |
2. 路徑長度 | 路徑上的分支數(shù)目 |
3. 樹的路徑長度 | 長度從根到每個結點的路徑長度之和 |
4. 帶權路徑長度 | 結點具有權值, 從該結點到根之間的路徑長度乘以結點的權值, 就是該結點的帶權路徑長度 |
5. 樹的帶權路徑長度 | 樹中所有葉子結點的帶權路徑長度之和 |
定義:
給定n個權值作為n個葉子結點, 構造出的一棵帶權路徑長度(WPL)最短的二叉樹,叫哈夫曼樹(), 也被稱為最最優(yōu)二叉樹.
WPL: Weighted Path Length of Tree 樹的帶權路徑長度
哈夫曼樹的特點:
1.權值越大的結點, 距離根節(jié)點越近;
2.樹中沒有度為1的結點, 哈夫曼樹的度只能是0 或 1;
3.帶權路徑長度最短的一棵二叉樹;
判斷下圖三個二叉樹那個是哈夫曼樹?
當然是WPL最小的樹啦, 即中間的二叉樹是也;
那么我們是如何手動構造出一棵哈夫曼樹的呢?
構造哈夫曼樹的步驟:
1.把所有結點的權值按照從小到大的順序進行排序;
2.取出根節(jié)點權值最小的兩棵二叉樹;
3.組成一棵新的二叉樹, 這課新二叉樹的根節(jié)點的權值是前面兩棵二叉樹權值的和
4.再將這棵新的二叉樹,以根節(jié)點的權值大小進行排序, 不斷重復1-2-3-4的步驟, 直到給定序列中的所有權值都被處理,我們就得到了一棵哈夫曼樹.
[圖解分析構造過程]
下面以序列{13,7,8,3}為例, 圖解構造哈夫曼樹的過程
首先對序列進行升序排列,得到{3,7,8,13};
取出權值最小的兩個結點3,7 , 組成一棵二叉樹,根節(jié)點是權值為10的結點;
在原序列中去除步驟2中已經(jīng)被使用了的3和7, 并把新的結點權值10加入到序列中并重新排序, 得到{8,10,13};
再次取出權值最小的兩個節(jié)點8,10, 組成一棵根節(jié)點為18的二叉樹, 然后我們去除序列中的8,10, 將18添加到序列中并排序, 得到了{13,18};
將序列{13,18}取出構成一棵新的二叉樹, 權值為31, 此時序列中只剩下了31這個結點, 他是這個哈夫曼樹的根節(jié)點;
至此, {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(); } // 設置左右子節(jié)點 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+"}"; } //根據(jù)權值對結點進行排序 // 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{ //哈夫曼樹的實現(xiàn): //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. 把存放權值的數(shù)組拿出來構建結點 //2. 把這些節(jié)點存放到集合中 for(int x : arr){ nodesList.add(new HTreeNode(x)); } while(nodesList.size() > 1){ //3. 利用集合的排序方法,可以根據(jù)權值對結點進行排序 Collections.sort(nodesList); // (當然了, 我們需要實現(xiàn)comparable接口中的copareTo方法), 在哪實現(xiàn)的? 在結點類中! //4. 不斷的循環(huán)從集合中取出兩個結點進行相加, 直到集合中只剩下一個結點才會終止循環(huán) HTreeNode leftNode = nodesList.get(0); HTreeNode rightNode = nodesList.get(1); HTreeNode parent = new HTreeNode(leftNode.weight + rightNode.weight); 建立父節(jié)點和左右子節(jié)點的關系(千萬不要忘了) //因為我們雖說是父節(jié)點和左右子節(jié)點, 還是要實實在在的于內存中體現(xiàn)出來的哈 parent.setLeftNode(leftNode); parent.setRightNode(rightNode); //5.從結合中移除用過的左右子節(jié)點, 添加父節(jié)點進去 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主要應用于:1. web開發(fā);2. Android開發(fā);3. 客戶端開發(fā);4. 網(wǎng)頁開發(fā);5. 企業(yè)級應用開發(fā);6. Java大數(shù)據(jù)開發(fā);7.游戲開發(fā)等。
感謝你能夠認真閱讀完這篇文章,希望小編分享的“Java數(shù)據(jù)結構之實現(xiàn)哈夫曼樹的示例分析”這篇文章對大家有幫助,同時也希望大家多多支持億速云,關注億速云行業(yè)資訊頻道,更多相關知識等著你來學習!
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內容。