前言
我想學過數據結構的小伙伴一定都認識哈夫曼，這位大神發明了大名鼎鼎的“最優二叉樹”，為了紀念他呢，我們稱之為“哈夫曼樹”。哈夫曼樹可以用於哈夫曼編碼，編碼的話學問可就大了，比如用於壓縮，用於密碼學等。今天一起來看看哈夫曼樹到底是什麼東東。
概念
當然，套路之一，首先我們要了解一些基本概念。
1、路徑長度：從樹中的一個結點到另一個結點之間的分支構成這兩個結點的路徑，路徑上的分支數目稱為路徑長度。
2、樹的路徑長度：從樹根到每一個結點的路徑長度之和，我們所說的完全二叉樹就是這種路徑長度最短的二叉樹。
3、樹的帶權路徑長度：如果在樹的每一個葉子結點上賦上一個權值，那麼樹的帶權路徑長度就等於根結點到所有葉子結點的路徑長度與葉子結點權值乘積的總和。
那麼我們怎麼判斷一棵樹是否為最優二叉樹呢，先看看下面幾棵樹：
他們的帶權長度分別為：
WPL1：7*2+5*2+2*2+4*2=36
WPL2：7*3+5*3+2*1+4*2=46
WPL3：7*1+5*2+2*3+4*3=35
很明顯，第三棵樹的帶權路徑最短（不信的小伙伴可以試一試，要是能找到更短的，估計能拿圖靈獎了），這就是我們所說的“最優二叉樹（哈夫曼樹）”，它的構建方法很簡單，依次選取權值最小的結點放在樹的底部，將最小的兩個連接構成一個新結點，需要注意的是構成的新結點的權值應該等於這兩個結點的權值之和，然後要把這個新結點放回我們需要構成樹的結點中繼續進行排序，這樣構成的哈夫曼樹，所有的存儲有信息的結點都在葉子結點上。
概念講完，可能有點小伙伴還是“不明覺厲”。
下面舉個例子構建一下就清楚了。
有一個字符串：aaaaaaaaaabbbbbaaaaaccccccccddddddfff
第一步，我們先統計各個字符出現的次數，稱之為該字符的權值。 a 15 ,b 5, c 8, d 6, f 3。
第二步，找去這裡面權值最小的兩個字符，b5和f3，構建節點。
然後將f3和b5去掉，現在是a15,c8,d6,fb8。
第三步，重複第二步，直到構建出只剩一個節點。
現在是dfb14,a15,c8。
最後，
ok,這樣我們的哈夫曼樹就構造完成了。
構建的步驟
按照上面的邏輯，總結起來，就是一下幾個步驟：
1.統計字符串中字符以及字符的出現次數；
2.根據第一步的結構，創建節點；
3.對節點權值升序排序；
4.取出權值最小的兩個節點，生成一個新的父節點；
5.刪除權值最小的兩個節點，將父節點存放到列表中；
6.重複第四五步，直到剩下一個節點；
7.將最後的一個節點賦給根節點。
java代碼
原理說完了，接下來是代碼實現了。
首先需要有個節點類來存放數據。
package huffman;/** * 節點類* @author yuxiu * */public class Node { public String code;// 節點的哈夫曼編碼public int codeSize;// 節點哈夫曼編碼的長度public String data;// 節點的數據public int count;// 節點的權值public Node lChild; public Node rChild; public Node() { } public Node(String data, int count) { this.data = data; this.count = count; } public Node(int count, Node lChild, Node rChild) { this.count = count; this.lChild = lChild; this.rChild = rChild; } public Node(String data, int count, Node lChild, Node rChild) { this.data = data; this.count = count; this.lChild = lChild; this.rChild = rChild; }}然後就是實現的過程了。
package huffman;import java.io.*;import java.util.*;public class Huffman { private String str;// 最初用於壓縮的字符串private String newStr = "";// 哈夫曼編碼連接成的字符串private Node root;// 哈夫曼二叉樹的根節點private boolean flag;// 最新的字符是否已經存在的標籤private ArrayList<String> charList;// 存儲不同字符的隊列相同字符存在同一位置private ArrayList<Node> NodeList;// 存儲節點的隊列15 16 /** * 構建哈夫曼樹* * @param str */ public void creatHfmTree(String str) { this.str = str; charList = new ArrayList<String>(); NodeList = new ArrayList<Node>(); // 1.統計字符串中字符以及字符的出現次數// 基本思想是將一段無序的字符串如ababccdebed放到charList裡，分別為aa,bbb,cc,dd,ee // 並且列表中字符串的長度就是對應的權值for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); // 從給定的字符串中取出字符flag = true; for (int j = 0; j < charList.size(); j++) { if (charList.get(j).charAt(0) == ch) {// 如果找到了同一字符String s = charList.get(j) + ch; charList.set(j, s); flag = false; break; } } if (flag) { charList.add(charList.size(), ch + ""); } } // 2.根據第一步的結構，創建節點for (int i = 0; i < charList.size(); i++) { String data = charList.get(i).charAt(0) + ""; // 獲取charList中每段字符串的首個字符int count = charList.get(i).length(); // 列表中字符串的長度就是對應的權值Node node = new Node(data, count); // 創建節點對象NodeList.add(i, node); // 加入到節點隊列} // 3.對節點權值升序排序Sort(NodeList); while (NodeList.size() > 1) {// 當節點數目大於一時// 4.取出權值最小的兩個節點，生成一個新的父節點// 5.刪除權值最小的兩個節點，將父節點存放到列表中Node left = NodeList.remove(0); Node right = NodeList.remove(0); int parentWeight = left.count + right.count;// 父節點權值等於子節點權值之和Node parent = new Node(parentWeight, left, right); NodeList.add(0, parent); // 將父節點置於首位} // 6.重複第四五步，就是那個while循環// 7.將最後的一個節點賦給根節點root = NodeList.get(0); } /** * 升序排序* * @param nodelist */ public void Sort(ArrayList<Node> nodelist) { for (int i = 0; i < nodelist.size() - 1; i++) { for (int j = i + 1; j < nodelist.size(); j++) { Node temp; if (nodelist.get(i).count > nodelist.get(j).count) { temp = nodelist.get(i); nodelist.set(i, nodelist.get(j)); nodelist.set(j, temp); } } } } /** * 遍歷* * @param node * 節點*/ public void output(Node node) { if (node.lChild != null) { output(node.lChild); } System.out.print(node.count + " "); // 中序遍歷if (node.rChild != null) { output(node.rChild); } } public void output() { output(root); }/** * 主方法* * @param args */ public static void main(String[] args) { Huffman huff = new Huffman();//創建哈弗曼對象huff.creatHfmTree("sdfassvvdfgsfdfsdfs");//構造樹}總結
以上就是基於JAVA實現哈夫曼樹的全部內容，希望這篇文章對大家學習使用JAVA能有所幫助。如果有疑問可以留言討論。