圖文詳解JAVA完成哈夫曼樹。本站提示廣大學習愛好者：（圖文詳解JAVA完成哈夫曼樹）文章只能為提供參考，不一定能成為您想要的結果。以下是圖文詳解JAVA完成哈夫曼樹正文
媒介
我想學過數據構造的小同伴必定都熟悉哈夫曼，這位年夜神創造了年夜名鼎鼎的“最優二叉樹”，為了留念他呢，我們稱之為“哈夫曼樹”。哈夫曼樹可以用於哈夫曼編碼，編碼的話學問可就年夜了，好比用於緊縮，用於暗碼學等。明天一路來看看哈夫曼樹究竟是甚麼東東。
概念
固然，套路之一，起首我們要懂得一些根本概念。
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能有所贊助。假如有疑問可以留言評論辯論。
