Java如何實現(xiàn)最優(yōu)二叉樹的哈夫曼算法

小編給大家分享一下Java如何實現(xiàn)最優(yōu)二叉樹的哈夫曼算法，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

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

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

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

下面是代碼：

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

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

}

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

public class HuffmanTree {
  
  protected HuffmanNode[] huffmanTree;
  
  public HuffmanTree(int[] leafs) {
    //異常條件判斷
    if (leafs.length <= 1) {
      throw new TreeException("葉子結(jié)點個數(shù)小于2，無法構(gòu)建哈夫曼樹");
    }
    //初始化儲存空間
    huffmanTree = new HuffmanNode[leafs.length*2-1];
    //構(gòu)造n棵只含根結(jié)點的二叉樹
    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é)點下標
      int miniNum_1 = selectMiniNum1();
      //獲取權(quán)值次小的結(jié)點下標
      int miniNum_2 = selectMiniNum2();
      if (miniNum_1 == -1 || miniNum_2 == -1) {
        return;
      }
      //兩個權(quán)值最小的結(jié)點合并為新節(jié)點
      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é)點下標
   * @return
   */
  private int selectMiniNum1() {
    //最小值
    int min = -1;
    //最小值下標
    int index = -1;
    //是否完成最小值初始化
    boolean flag = false;
    //遍歷一遍
    for (int i = 0; i < huffmanTree.length; i++) {
      //排空、只看根結(jié)點，否則跳過
      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é)點下標
   * @return
   */
  private int selectMiniNum2() {
    //次小值
    int min = -1;
    //是否完成次小值初始化
    boolean flag = false;
    //最小值下標（調(diào)用上面的方法）
    int index = selectMiniNum1();
    //最小值都不存在，則次小值也不存在
    if (index == -1) {
      return -1;
    }
    //次小值下標
    int index2 = -1;
    //遍歷一遍
    for (int i = 0; i < huffmanTree.length; i++) {
      //最小值不要、排空、只看根結(jié)點，否則跳過
      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;
  }

}

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

}

測試結(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]

圖形表示：

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

}

測試結(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]

圖形表示：

以上是“Java如何實現(xiàn)最優(yōu)二叉樹的哈夫曼算法”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！