Simple implementation of Huffman algorithm for Java optimal binary tree

The optimal binary tree is also called Huffman tree. The straight point is that each node has weight. We let the large value be close to the root and the small value be far from the root to minimize the overall weight (weighted path length).

I think the idea of Huffman algorithm is mentioned above, The idea of its algorithm implementation is as follows: extract the two with the smallest weight from the root node (involving sorting, but my implementation code does not strictly sort, only compare) to merge a new root node and re join the sorting (the two extracted nodes naturally become non root nodes). This cycle continues until the merger is completed, and we get an optimal binary tree, Huffman tree.

Note: (1) if the Huffman tree has n leaf nodes, we can deduce that it has n-1 branch nodes. Therefore, when defining the huffmannode type array named HuffmanTree, I define the length as 2 * n-1. (2) the sorting correlation is not well done here, but it is implemented for implementation and will be improved gradually in the future. (3) Theoretically, Huffman tree should not be limited to numerical values, but can be compared, but it is only represented by int.

Here is the code:

Firstly, the Huffman tree node is defined

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 + "]";
  }

}

Define the exception class of Huffman tree

public class TreeException extends RuntimeException {

  private static final long serialVersionUID = 1L;

  public TreeException() {}

  public TreeException(String message) {
    super(message);
  }

}

Coding implementation (the processing is not so efficient)

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

}

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

}

Test result 1

Graphical representation:

Test class 2

public class HuffmanTreeTester {

  public static void main(String[] args) {
    int[] leafs = {2,3};
    HuffmanTree tree = new HuffmanTree(leafs);
    HuffmanNode[] nodeList = tree.huffmanTree;
    for (HuffmanNode node : nodeList) {
      System.out.println(node);
    }
  }

}

Test result 2

Graphical representation:

The above is the whole content of this article. I hope it will help you in your study, and I hope you will support us a lot.