PROGRAMMING:Huffman coding and decoding
Write a Huffman coding and decoding program.
According to the word frequency from small to large, the word frequency of each character (no more than 10) is given. According to the word frequency, the Huffman tree is constructed, the Huffman code of each character is given, and the given sentence is decoded.
In order to ensure the uniqueness of the constructed Huffman tree, this paper makes the following restrictions:
(1) When selecting the two binary trees with the minimum weight of the root node, the one with the smaller weight is selected as the left subtree.
(2) If the weights of root nodes of multiple binary trees are equal, they are divided into left and right according to the order. The first one is the left subtree, and the second one is the right subtree.
When generating Huffman code, the left branch of Huffman tree is marked as 0, and the right branch is marked as 1.
###Input format:
Enter the number of characters in the first line;
In the second line, input the corresponding characters and their word frequency;
The third line is the string to be decoded.
###Output format:
Firstly, the codes of all characters are output in the order of the tree, and each code occupies one line;
The last line outputs the original text to be decoded, plus the word original.
There are no spaces in the output
###Input example:
```in
three
m1n1c2
ten thousand one hundred and ten
```
###Output example:
```out
c:0
m:10
n:11
original:mnc
```
answer：If there is no answer, please comment
According to the word frequency from small to large, the word frequency of each character (no more than 10) is given. According to the word frequency, the Huffman tree is constructed, the Huffman code of each character is given, and the given sentence is decoded.
In order to ensure the uniqueness of the constructed Huffman tree, this paper makes the following restrictions:
(1) When selecting the two binary trees with the minimum weight of the root node, the one with the smaller weight is selected as the left subtree.
(2) If the weights of root nodes of multiple binary trees are equal, they are divided into left and right according to the order. The first one is the left subtree, and the second one is the right subtree.
When generating Huffman code, the left branch of Huffman tree is marked as 0, and the right branch is marked as 1.
###Input format:
Enter the number of characters in the first line;
In the second line, input the corresponding characters and their word frequency;
The third line is the string to be decoded.
###Output format:
Firstly, the codes of all characters are output in the order of the tree, and each code occupies one line;
The last line outputs the original text to be decoded, plus the word original.
There are no spaces in the output
###Input example:
```in
three
m1n1c2
ten thousand one hundred and ten
```
###Output example:
```out
c:0
m:10
n:11
original:mnc
```
answer：If there is no answer, please comment