Basic concepts of Huffman tree

The basic concept of Huffman tree ：

（1） route ： It consists of branches from one node to another
（2） The length of the path ： Number of branches on the path a→d The path length of ＝ 2
（3） The path length of the tree ： The sum of the path length from the tree root to each node . Case diagram ：10
（4） power ： A quantity given to an entity , It is a numerical description of the attributes of entities . If the nodes of the tree have weights , That is, the weighted tree .
（5） The weighted path length of the node ： The product of the path length from node to root and the weight on the node d Weighted path length ＝72=14
（6） Weighted path length of tree ： The sum of the weighted path lengths of all leaf nodes in the tree . Case diagram ：27+25+22+2*4=36
（7） Huffman tree （Huffman）： The best binary tree , The tree with the smallest weighted path length

The characteristics of Huffman tree

• The path length from the node with large weight to the root node is short ;
• The path length from the node with small weight to the root node is long .

Ø There is no degree in Huffman coding tree 1 The node of ;
Ø If given n Weight （n Leaf node ）, Then the total number of points of Huffman tree is 2n-1;
Ø The height of Huffman tree does not exceed n.

The construction algorithm of Huffman tree ：

Huffman code ：

v Prefix encoding ： The encoding of any character is not a prefix of the encoding of another character .
Such as ： character a、b、c、d The codes of the two are respectively 0、1、01、10, be a The code of is c The prefix of the encoding ,b The code of is d Coded prefix , This code is not a prefix code .
When decoding , about 01011011 The decoding result of will not be unique .
v Huffman code
For a tree with n A leafy Huffman tree , Assign 0, The right branch gives 1, Then the path from the root to each leaf , Form a binary string respectively , This binary string is called Huffman code .
Do Huffman coding , Build Huffman tree first .
Huffman coding is prefix coding , And it's the best prefix code .