2494哈夫曼编码
6732+
作者：crxis 发布：2017-06-11 分类：二叉树
题目大意：对字符串进行哈夫曼编码，使得编码长度最短，输出各个字符的编码以及整个字符串的编码。
题目描述
请对文本中的字符进行哈夫曼编码，除空格外，其他不可见字符不需要编码。
输入
输入一行，一个字符串，行末无不可见字符
输出
输出各个字符的编码，以及整个字符串的编码。
样例输入
CAS;CAT;SAT;AT
样例输出
; 00
T 01
A 10
S 110
C 111
11110110001111001001101001001001
提示
字符串长度不超过1000，除了空格外，字符串不含有其他不可见字符。
说明
编码不唯一，但长度一定相同，都是最小。11010111011101000011111000011000也是可行的，只是各个字符的编码不一样了而已。
解题思路
首先统计各个字符出现的次数，然后每次找最小的两个合并在一起，用结构体记录这棵最优二叉树的结点的左儿子、右儿子，如果没有儿子即是叶子结点，该字符的编码为从根到它边上的编码，左边编0，右边编1，在遍历这棵哈夫曼树的同时，输出并记录每个字符的编码，最后依次输出来即整个字符串的编码。
程序实现
