Ask for information on Huffman trees in Data Structures

The Huffman tree is:

The weighted path length of a tree is the sum of the weighted path lengths of all leaf nodes in the tree, and the weighted path length of a node is the product of the path length from the node to the root node and the weights on the node.

wpl=3*（1+2）+2*3+2*（4+5）=33

According to the properties of the binary tree: n2 = n0 - 1, the column equations get {n2 = n0 - 1, n0 + n2 = 199}, and the solution of the equations gives n0 = 100, so there are 100 leaf nodes.

Huffman tree: Given n weights as n leaf nodes, a binary tree is constructed, and if the length of the weighted path reaches the minimum, such a binary tree is called the optimal binary tree, also known as a huffman tree. The Huffman tree is the tree with the shortest weighted path length, and the nodes with larger weights are closer to the roots.

Structure of the Huffman tree:

Suppose the given weights are as follows: 3, 5, 7, 8, 10, 15;

First, take the two smallest numbers in the set: 3+5=8, then delete the values of 3 and 5 in the set, put 8 into the original set, and the original set becomes: 7,8,8,10,15;

Then take the 2 smallest numbers from 7, 8, 8, 10, and 15 to form a tree.

Then take the 2 smallest numbers from 8, 10, 15, and 15 to form a tree:

Then take the two smallest numbers from 15, 15, and 18: 15 and 15 to form the tree:

Finally, 18,30 is used to form a tree (at this point, there are no elements in the set, and a Huffman tree is formed).

Hope you understand!!

The first step is sorting.

The composition is as follows Thanks for reminding me that I was careless ......

Character version Copy it into Notepad and read it.

**o***

**o***o***

*19*21**o**32***

**o***o***

**o*6*7*10***

Step 1: Sort 2 4 5 9

Step 2: Pick out the 2 smallest 2 4 to construct the leaves.

Step 3: Judge that 6 is not greater than 5 or 9 (the smallest 2 of the remaining leaves) = 》 grow in the same direction, and obtain:

Step 4: Continue to grow.

The weight of 2 4 is 2*3+4*3+5*2+9*1=37

It can also be 20 + 11 + 6 = 37

Example Sort 6 7 13 16 18 30

26 26 is greater than 16 or 18 = "branch growth.

The smallest 2 numbers are 26 30.

The final result is 90

6 7 Weight 219

90+56+26+13+34 or 6*4+7*4+13*3+30*2+16*2+18*2

As the name suggests, this is not a real tree, it is actually a model like the root system of a tree, a pyramid, and this model can be useful, it can help us understand easily, understand some related problems, it is very creative, it is very valuable.

The weight of the node in the problem Path length in the tree = 131