溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下Java如何實現最優二叉樹的哈夫曼算法，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
最優二叉樹也稱哈夫曼樹，講的直白點就是每個結點都帶權值，我們讓大的值離根近、小的值離根遠，實現整體權值（帶權路徑長度）最小化。
哈夫曼算法的思想我認為就是上面講的，而它的算法實現思路是這樣的：
從根結點中抽出權值最小的兩個（涉及排序，但是我這個實現代碼沒做嚴格的排序，只有比較）合并出新的根結點重新加入排序（被抽出來的兩個自然是變成非根結點了啊），就這樣循環下去，直到合并完成，我們得到一顆最優二叉樹——哈夫曼樹。
說明：
（1）哈夫曼樹有n個葉子結點，則我們可以推出其有n-1個分支結點。因此我在定義名為huffmanTree的HuffmanNode類型數組時定義長度為2*n-1。
（2）這里排序相關沒有做得很好，只是為了實現而實現，以后慢慢完善。
（3）理論上講哈夫曼樹應該是不僅僅局限于數值，能compare就行，但這里只用int表示。
下面是代碼：
首先定義哈夫曼樹結點
public class HuffmanNode {
private int weight = -1;
private int parent = -1;
private int left = -1;
private int right = -1;
public HuffmanNode(int weight) {
super();
this.weight = weight;
}
public HuffmanNode(int weight, int left, int right) {
super();
this.weight = weight;
this.left = left;
this.right = right;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getParent() {
return parent;
}
public void setParent(int parent) {
this.parent = parent;
}
public int getLeft() {
return left;
}
public void setLeft(int left) {
this.left = left;
}
public int getRight() {
return right;
}
public void setRight(int right) {
this.right = right;
}
@Override
public String toString() {
return "HuffmanNode [weight=" + weight + ", parent=" + parent + ","
+ " left=" + left + ", right=" + right + "]";
}
}定義一下哈夫曼樹的異常類
public class TreeException extends RuntimeException {
private static final long serialVersionUID = 1L;
public TreeException() {}
public TreeException(String message) {
super(message);
}
}編碼實現（做的處理不是那么高效）
public class HuffmanTree {
protected HuffmanNode[] huffmanTree;
public HuffmanTree(int[] leafs) {
//異常條件判斷
if (leafs.length <= 1) {
throw new TreeException("葉子結點個數小于2，無法構建哈夫曼樹");
}
//初始化儲存空間
huffmanTree = new HuffmanNode[leafs.length*2-1];
//構造n棵只含根結點的二叉樹
for (int i = 0; i < leafs.length; i++) {
HuffmanNode node = new HuffmanNode(leafs[i]);
huffmanTree[i] = node;
}
//構造哈夫曼樹的選取與合并
for (int i = leafs.length; i < huffmanTree.length; i++) {
//獲取權值最小的結點下標
int miniNum_1 = selectMiniNum1();
//獲取權值次小的結點下標
int miniNum_2 = selectMiniNum2();
if (miniNum_1 == -1 || miniNum_2 == -1) {
return;
}
//兩個權值最小的結點合并為新節點
HuffmanNode node = new HuffmanNode(huffmanTree[miniNum_1].getWeight() +
huffmanTree[miniNum_2].getWeight(), miniNum_1, miniNum_2);
huffmanTree[i] = node;
huffmanTree[miniNum_1].setParent(i);
huffmanTree[miniNum_2].setParent(i);
}
}
/**
* 獲取權值最小的結點下標
* @return
*/
private int selectMiniNum1() {
//最小值
int min = -1;
//最小值下標
int index = -1;
//是否完成最小值初始化
boolean flag = false;
//遍歷一遍
for (int i = 0; i < huffmanTree.length; i++) {
//排空、只看根結點，否則跳過
if (huffmanTree[i] == null || huffmanTree[i].getParent() != -1) {
continue;
} else if (!flag) { //沒初始化先初始化然后跳過
//初始化
min = huffmanTree[i].getWeight();
index = i;
//以后不再初始化min
flag = true;
//跳過本次循環
continue;
}
int tempWeight = huffmanTree[i].getWeight();
//低效比較
if (tempWeight < min) {
min = tempWeight;
index = i;
}
}
return index;
}
/**
* 獲取權值次小的結點下標
* @return
*/
private int selectMiniNum2() {
//次小值
int min = -1;
//是否完成次小值初始化
boolean flag = false;
//最小值下標（調用上面的方法）
int index = selectMiniNum1();
//最小值都不存在，則次小值也不存在
if (index == -1) {
return -1;
}
//次小值下標
int index2 = -1;
//遍歷一遍
for (int i = 0; i < huffmanTree.length; i++) {
//最小值不要、排空、只看根結點，否則跳過
if (index == i || huffmanTree[i] == null || huffmanTree[i].getParent() != -1) {
continue;
} else if (!flag) { //沒初始化先初始化然后跳過
//初始化
min = huffmanTree[i].getWeight();
index2 = i;
//以后不再初始化min
flag = true;
//跳過本次循環
continue;
}
int tempWeight = huffmanTree[i].getWeight();
//低效比較
if (tempWeight < min) {
min = tempWeight;
index2 = i;
}
}
return index2;
}
}測試類1
public class HuffmanTreeTester {
public static void main(String[] args) {
int[] leafs = {1, 3, 5, 6, 2, 22, 77, 4, 9};
HuffmanTree tree = new HuffmanTree(leafs);
HuffmanNode[] nodeList = tree.huffmanTree;
for (HuffmanNode node : nodeList) {
System.out.println(node);
}
}
}測試結果1
HuffmanNode [weight=1, parent=9, left=-1, right=-1]
HuffmanNode [weight=3, parent=10, left=-1, right=-1]
HuffmanNode [weight=5, parent=11, left=-1, right=-1]
HuffmanNode [weight=6, parent=12, left=-1, right=-1]
HuffmanNode [weight=2, parent=9, left=-1, right=-1]
HuffmanNode [weight=22, parent=15, left=-1, right=-1]
HuffmanNode [weight=77, parent=16, left=-1, right=-1]
HuffmanNode [weight=4, parent=11, left=-1, right=-1]
HuffmanNode [weight=9, parent=13, left=-1, right=-1]
HuffmanNode [weight=3, parent=10, left=0, right=4]
HuffmanNode [weight=6, parent=12, left=1, right=9]
HuffmanNode [weight=9, parent=13, left=7, right=2]
HuffmanNode [weight=12, parent=14, left=3, right=10]
HuffmanNode [weight=18, parent=14, left=8, right=11]
HuffmanNode [weight=30, parent=15, left=12, right=13]
HuffmanNode [weight=52, parent=16, left=5, right=14]
HuffmanNode [weight=129, parent=-1, left=15, right=6]
圖形表示：
測試類2
public class HuffmanTreeTester {
public static void main(String[] args) {
int[] leafs = {2, 4, 5, 3};
HuffmanTree tree = new HuffmanTree(leafs);
HuffmanNode[] nodeList = tree.huffmanTree;
for (HuffmanNode node : nodeList) {
System.out.println(node);
}
}
}測試結果2
HuffmanNode [weight=2, parent=4, left=-1, right=-1]
HuffmanNode [weight=4, parent=5, left=-1, right=-1]
HuffmanNode [weight=5, parent=5, left=-1, right=-1]
HuffmanNode [weight=3, parent=4, left=-1, right=-1]
HuffmanNode [weight=5, parent=6, left=0, right=3]
HuffmanNode [weight=9, parent=6, left=1, right=2]
HuffmanNode [weight=14, parent=-1, left=4, right=5]
圖形表示：
以上是“Java如何實現最優二叉樹的哈夫曼算法”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
