Shulou(Shulou.com)06/02 Report--

This article will explain in detail how to implement the Huffman algorithm of the Java optimal binary tree. The content of the article is of high quality, so the editor will share it for you as a reference. I hope you will have some understanding of the relevant knowledge after reading this article.

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

I think the idea of Huffman algorithm is mentioned above, and the implementation idea of its algorithm is as follows: extract the two with the least weight from the root node (involving sorting, but my implementation code does not do strict sorting. Only compare) merge new root nodes and re-join sorting (the two extracted naturally become non-root nodes), and cycle until the merge is completed. We get an optimal binary tree-Huffman tree.

Explanation: (1) if Huffman tree has n leaf nodes, then we can deduce that Huffman tree has one branch node. So when I define an array of HuffmanNode types named huffmanTree, I define the length as 2*n-1. (2) the ranking correlation here is not done very well, it is only realized for the sake of realization, and it will be perfected gradually later. (3) in theory, Huffman tree should not only be limited to numerical values, but can compare, but it is only expressed by int here.

Here is the code:

First define the Huffman tree node

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 the 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) {

/ / abnormal condition judgment if (leafs.length

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.