如何進(jìn)行Java最優(yōu)二叉樹的哈夫曼算法的簡(jiǎn)單實(shí)現(xiàn)

這篇文章將為大家詳細(xì)講解有關(guān)如何進(jìn)行Java最優(yōu)二叉樹的哈夫曼算法的簡(jiǎn)單實(shí)現(xiàn)，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

最優(yōu)二叉樹也稱哈夫曼樹，講的直白點(diǎn)就是每個(gè)結(jié)點(diǎn)都帶權(quán)值，我們讓大的值離根近、小的值離根遠(yuǎn)，實(shí)現(xiàn)整體權(quán)值（帶權(quán)路徑長度）最小化。

哈夫曼算法的思想我認(rèn)為就是上面講的，而它的算法實(shí)現(xiàn)思路是這樣的：從根結(jié)點(diǎn)中抽出權(quán)值最小的兩個(gè)（涉及排序，但是我這個(gè)實(shí)現(xiàn)代碼沒做嚴(yán)格的排序，只有比較）合并出新的根結(jié)點(diǎn)重新加入排序（被抽出來的兩個(gè)自然是變成非根結(jié)點(diǎn)了?。?，就這樣循環(huán)下去，直到合并完成，我們得到一顆最優(yōu)二叉樹——哈夫曼樹。

說明：（1）哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)，則我們可以推出其有n-1個(gè)分支結(jié)點(diǎn)。因此我在定義名為huffmanTree的HuffmanNode類型數(shù)組時(shí)定義長度為2*n-1。（2）這里排序相關(guān)沒有做得很好，只是為了實(shí)現(xiàn)而實(shí)現(xiàn)，以后慢慢完善。（3）理論上講哈夫曼樹應(yīng)該是不僅僅局限于數(shù)值，能compare就行，但這里只用int表示。

下面是代碼：

首先定義哈夫曼樹結(jié)點(diǎn)

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);

  }}

編碼實(shí)現(xiàn)（做的處理不是那么高效）

public class HuffmanTree {    

protected HuffmanNode[] huffmanTree;   

 public HuffmanTree(int[] leafs) {    

//異常條件判斷    if (leafs.length <= 1) {      

throw new TreeException("葉子結(jié)點(diǎn)個(gè)數(shù)小于2，無法構(gòu)建哈夫曼樹");    }   

 //初始化儲(chǔ)存空間    huffmanTree = new HuffmanNode[leafs.length*2-1];    

//構(gòu)造n棵只含根結(jié)點(diǎn)的二叉樹    for (int i = 0; i < leafs.length; i++) {      

HuffmanNode node = new HuffmanNode(leafs[i]);      

huffmanTree[i] = node;    }    

//構(gòu)造哈夫曼樹的選取與合并    for (int i = leafs.length; i < huffmanTree.length; i++) {     

 //獲取權(quán)值最小的結(jié)點(diǎn)下標(biāo)      int miniNum_1 = selectMiniNum1();     

 //獲取權(quán)值次小的結(jié)點(diǎn)下標(biāo)      int miniNum_2 = selectMiniNum2();      

if (miniNum_1 == -1 || miniNum_2 == -1) {        return;

      }     

 //兩個(gè)權(quán)值最小的結(jié)點(diǎn)合并為新節(jié)點(diǎn)     

 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);

    }  }   

 /**   * 獲取權(quán)值最小的結(jié)點(diǎn)下標(biāo)   

* @return   */  private int selectMiniNum1() {    

//最小值    int min = -1;   

 //最小值下標(biāo)    int index = -1;   

 //是否完成最小值初始化    boolean flag = false;   

 //遍歷一遍    for (int i = 0; i < huffmanTree.length; i++) {      

//排空、只看根結(jié)點(diǎn)，否則跳過      

if (huffmanTree[i] == null || huffmanTree[i].getParent() != -1) {       

 continue;      } 

else if (!flag) {   //沒初始化先初始化然后跳過        

//初始化        min = huffmanTree[i].getWeight();       

 index = i;       

 //以后不再初始化min        flag = true;       

 //跳過本次循環(huán)        continue;  

    }      int tempWeight = huffmanTree[i].getWeight();      

//低效比較      if (tempWeight < min) {       

 min = tempWeight;        

index = i;    

  }    

}    return index;  }    

/**   * 獲取權(quán)值次小的結(jié)點(diǎn)下標(biāo)   * @return   */  private int selectMiniNum2() {    

//次小值    int min = -1;    

//是否完成次小值初始化    boolean flag = false;    

//最小值下標(biāo)（調(diào)用上面的方法）    int index = selectMiniNum1();   

 //最小值都不存在，則次小值也不存在    if (index == -1) {     

 return -1;    }    

//次小值下標(biāo)    int index2 = -1;   

 //遍歷一遍    for (int i = 0; i < huffmanTree.length; i++) {      

//最小值不要、排空、只看根結(jié)點(diǎn)，否則跳過     

 if (index == i || huffmanTree[i] == null || huffmanTree[i].getParent() != -1) {        

continue; 

     } 

else if (!flag) {  

 //沒初始化先初始化然后跳過        

//初始化        min = huffmanTree[i].getWeight();       

 index2 = i;       

 //以后不再初始化min        flag = true;        

//跳過本次循環(huán)        continue;    

  }      int tempWeight = huffmanTree[i].getWeight();     

 //低效比較      if (tempWeight < min) {        min = tempWeight;       

 index2 = i;    

  }   

 }    return index2;

  }

}

測(cè)試類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);

    } 

 }

}

測(cè)試結(jié)果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]

圖形表示：

測(cè)試類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);    }  }}

測(cè)試結(jié)果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]

關(guān)于如何進(jìn)行Java最優(yōu)二叉樹的哈夫曼算法的簡(jiǎn)單實(shí)現(xiàn)就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。