问题 1761. -- 算法6-13:自顶向下的赫夫曼编码

1761: 算法6-13:自顶向下的赫夫曼编码

时间限制: 1 Sec  内存限制: 32 MB
献花: 11  解决: 9
[献花][花圈]

题目描述

在本题中,我们将要讨论的是自顶向下的赫夫曼编码算法。从根出发,遍历整棵赫夫曼树从而求得各个叶子结点所表示的字符串。算法的关键部分可以表示如下:
在本题中,读入n个字符所对应的权值,生成赫夫曼编码,并依次输出计算出的每一个赫夫曼编码。

输入

输入的第一行包含一个正整数n,表示共有n个字符需要编码。其中n不超过100。
第二行中有n个用空格隔开的正整数,分别表示n个字符的权值。

输出

共n行,每行一个字符串,表示对应字符的赫夫曼编码。

样例输入

8
5 29 7 8 14 23 3 11

样例输出

0110
10
1110
1111
110
00
0111
010

提示

在本题中,与上一题不同的是在求赫夫曼编码的过程中,使用了从根出发开始遍历整棵赫夫曼树的自顶向下的算法。通过这两道题目的联系,应该能够熟练的掌握赫夫曼树和赫夫曼编码的构造和使用方法了。

来源

[献花][花圈]