霍夫曼编码,对输入的字符集和各个字符对应的权值,例如A={a,b,c,d,e,f,g,h},各个字符对应的权值为{5,29,7,8,14,23,3,11},求出每个字符的霍夫曼编码。
【输入形式】
输入若干个字符(1 <= n <= 26),其权值为int型。
输入数据的第一行的整数n,表示字符数;接下来的n行是字符集,一行一个字符;最后一行是各字符的权值,以空格分隔。
【输出形式】
每个字符(节点)的霍夫曼编码。参见样例输出。
【样例输入】
4
a
b
c
d
1 3 7 22
【样例输出】
a:000
b:001
c:01
d:1
【样例说明】
提示:
1、将最小两个子树合并过程中一定要从前向后去查找两个最小子树,最小子树作为新结点的左子树,次小子树作为新结点的右子树,编码过程中左子树定义为0,右子树定义为1
2、另外:一般原则要求:
若有重复权值结点,原来森林中的结点优先选择(即深度小的结点优先,以确保最终总树深较浅并相对平衡)。新生成的权值和的结点后用。
1