当前位置:首页 > 数据结构 > 二叉树 > 正文
2494哈夫曼编码
5237+

题目大意:对字符串进行哈夫曼编码,使得编码长度最短,输出各个字符的编码以及整个字符串的编码。

题目描述

请对文本中的字符进行哈夫曼编码,除空格外,其他不可见字符不需要编码。

输入

输入一行,一个字符串,行末无不可见字符

输出

输出各个字符的编码,以及整个字符串的编码。

样例输入

CAS;CAT;SAT;AT

样例输出

; 00
T 01
A 10
S 110
C 111
11110110001111001001101001001001

提示

字符串长度不超过1000,除了空格外,字符串不含有其他不可见字符。

说明

编码不唯一,但长度一定相同,都是最小。11010111011101000011111000011000也是可行的,只是各个字符的编码不一样了而已。

解题思路

首先统计各个字符出现的次数,然后每次找最小的两个合并在一起,用结构体记录这棵最优二叉树的结点的左儿子、右儿子,如果没有儿子即是叶子结点,该字符的编码为从根到它边上的编码,左边编0,右边编1,在遍历这棵哈夫曼树的同时,输出并记录每个字符的编码,最后依次输出来即整个字符串的编码。

程序实现

2494哈夫曼编码:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!