CSP-J 入门级 · CSP 2023 入门级第一轮 第 10 题

假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为 $5\%,9\%,12\%,13\%,16\%,45\%$。请问以下哪个选项是字符abcdef分别对应的一组哈夫曼编码?

这道题考哈夫曼编码。拿到频率表别急着写代码，先按大小排序，把最小的两个（a和b）拎出来合并，接着看新的最小两个继续合，直到只剩一个根。最后看哪棵树的叶子路径能凑出选项A的编码。

最容易栽跟头的是把合并顺序搞错，比如先合并了c和d，那后面e和f的编码长度就全乱了；还有很多人以为编码长度和频率是一一对应的，其实哈夫曼树只要满足“前缀码”且“频率高的短、频率低的长”即可，左右支路标0还是标1都可以互换，所以算出来的编码跟选项A可能只是01反了，别慌，只要结构对就行。

考点与概念

哈夫曼编码的核心是建一棵二叉树：所有字符按频率从小到大排，每次把当前最小（或次小）的两个节点合并成一个新节点，新节点频率为两者之和，再把新节点放回队列。重复直到只剩一个节点（根）。从根到每个叶子画一条路径，左支标0、右支标1（或反过来）就得到编码。高频字符离根近，编码短；低频字符离根远，编码长。只要满足“前缀码”（没有一个编码是另一个的前缀）且符合频率长短关系，左右支路标号互换都是合法的。

命题视角

这类题喜欢用一组频率让你还原编码，考点不在死记公式，而在你是否真的会“合并”：先把a(5%)和b(9%)合并成14%，再把c(12%)和d(13%)合并成25%，接着看队列里最小的两个是14%和e(16%)，合并成30%，再合并25%和30%成55%，最后55%和f(45%)合并成100%（根）。命题人常把左右支路标号故意反着写，让你以为结果不对，其实只要树结构对，编码就合法。