Java implementation of Huffman tree

O(∩_∩)O~~

summary

I think everyone who has studied data structure must know Huffman. The great God invented the famous "optimal binary tree". In memory of him, we call it "Huffman tree". Huffman tree can be used for Huffman coding, and the knowledge of coding can be great, such as compression, cryptography and so on. Today, let's see what the Huffman tree is.

concept

Of course, one of the routines, first we need to understand some basic concepts.

1. Path length: the branches from one node to another in the tree form the path of these two nodes. The number of branches on the path is called path length.

2. The path length of the tree: the sum of the path length from the tree root to each node. The complete binary tree we call is the binary tree with the shortest path length.

3. Weighted path length of tree: if a weight is assigned to each leaf node of the tree, the weighted path length of the tree is equal to the sum of the product of the path length from the root node to all leaf nodes and the weight of leaf nodes.

So how do we judge whether a tree is the optimal binary tree? Let's take a look at the following trees:

Their weighted lengths are:

WPL1：7*2+5*2+2*2+4*2=36

WPL2：7*3+5*3+2*1+4*2=46

WPL3：7*1+5*2+2*3+4*3=35

Obviously, The third tree has the shortest weighted path (you can try it if you don't believe it. If you can find a shorter one, you may win the Turing Award). This is what we call the "optimal binary tree (Huffman tree)" , its construction method is very simple. Select the node with the smallest weight in turn and put it at the bottom of the tree, and connect the two smallest nodes to form a new node. It should be noted that the weight of the new node should be equal to the sum of the weights of the two nodes, and then put the new node back into the node that we need to form the tree to continue sorting. In this way, the Huffman tree is formed, All nodes storing information are on leaf nodes.

After the concept is finished, it may be a little partner or "unclear and sharp". Let's take an example to build it.

There is a string: aaaaaaaaaabbbbbaaaaccccccddddfff

The first step is to count the number of occurrences of each character, which is called the weight of the character. a 15,b 5,c 8,d 6,f 3。

The second step is to find the two characters with the smallest weight, B5 and F3, and build the node.

And then we take out F3 and B5, and now it's A15, C8, D6, fb8.

Step 3, repeat step 2 until there is only one node left.

Now it's dfb14, A15, C8.

last,

OK, so our Huffman tree is constructed.

Steps to build

According to the above logic, the following steps can be summarized:

1. Count the characters in the string and the occurrence times of characters;

2. Create nodes according to the structure in step 1;

3. Sort node weights in ascending order;

4. Take out the two nodes with the smallest weight and generate a new parent node;

5. Delete the two nodes with the smallest weight and store the parent node in the list;

6. Repeat steps 4 and 5 until there is one node left;

7. Assign the last node to the root node.

java code

After the principle is finished, the next is the code implementation.

First, you need a node class to store data.

Then is the implementation process.