前言
我想學過數據結構的小伙伴一定都認識哈夫曼，這位大神發明了大名鼎鼎的“最優二叉樹”，為了紀念他呢，我們稱之為“哈夫曼樹”。哈夫曼樹可以用于哈夫曼編碼，編碼的話學問可就大了，比如用于壓縮，用于密碼學等。今天一起來看看哈夫曼樹到底是什么東東。
概念
當然，套路之一，首先我們要了解一些基本概念。
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代碼
原理說完了，接下來是代碼實現了。
首先需要有個節點類來存放數據。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
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; }} |
然后就是實現的過程了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
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能有所幫助。如果有疑問可以留言討論。
