企业官网建设流程全解析

408前缀编码：为什么字符只能放在叶子上？

这道题对应2020年408第42题。已核对题面转载与新东方当年答案解析；没有取得教育考试机构发布的原卷扫描件，因此不把网络转载标成官方原件。

原题给定至少两个字符的不等长二进制编码，最长L位，前两问针对已经具有前缀特性的码表，询问存储结构和译码过程；第三问询问如何判断一组编码的前缀特性。原题没有要求完整C程序和在线判题格式。

题面：转载版。过程核对：新东方2020答案解析，第6页。下面的码表、输入输出和异常处理是实现演示，不是原题样例。

1. 我的入口：先想清楚“前缀”意味着什么

例如A=01、B=011，01是011开头的一部分，所以A的码字是B的前缀。读到01时，不能直接断定该输出A，后面还可能有一个1。

这里要说准确：不满足前缀特性，不等于必然不能唯一译码。这个例子的每个码字以0开始，后面只有一个或两个1，可以根据后续0或输入结束确认边界；它不能在刚读到01时立即决定输出。

前缀码提供的便利是“即时译码”：读完一个码字就能确定当前字符，无需再等下一位。前缀码必然唯一可译，但反过来不成立。MIT信息论讲义，第6.2节

2. 两种选择，自然对应二叉分支

我的第一反应是：每读一位，只可能遇到0或1。从根开始，0走左孩子、1走右孩子，就能把编码真正放到一棵二叉树里。

演示码表如下：

每条码字对应一条根到终点的路径。为了表达“路径已经是一个完整编码”，结点除了两个孩子，还需要字符和终止标记：

typedef struct Node { struct Node *child[2]; char ch; int is_char; } Node;

is_char不是装饰。建树时要区别“已有一段路径”和“这段路径已经是某个字符的完整编码”。只看结点是否存在，不能判断有没有前缀冲突。

这里是在保存给定编码的二叉Trie，不是按频率构造哈夫曼树。题目没有给权重，也没有要求最小平均码长，不需要先重新计算一套编码。一般的前缀码树也不要求每个内部结点都恰好有两个孩子。普林斯顿算法课程

3. 前缀冲突，就是字符终点还想继续向下

如果把A=01、B=011放进同一棵树，B的路径会经过A的终点。也就是说，A结点下面还有字符B。

因此，在正确的编码树中，保存字符的终点必须是叶子。树的形状把字符串关系变成了结点关系：一个码字是另一个码字的前缀，等价于它的终点是另一个终点的祖先。

但只写“检查字符是否都在叶子上”还不够：若两个不同字符都编码成01，它们会落在同一个终点。即使那个结点是叶子，也不能给它保存两个不同字符。重复码字必须另行拒绝。

4. 插入顺序不同，检查位置也不同

只举“先01后011”会漏掉另一种情况。两种顺序都要处理：

插入代码对应三个检查：途中遇到is_char，终点已有is_char，终点已有孩子。共同约束是：新的字符终点不能落在旧终点的上方、下方或同一个位置。

每次合法插入只增加一条路径，并保持所有字符终点互不为祖先。三种检查恰好覆盖已有码字是新码字前缀、新码字是已有码字前缀，以及码字相同的情况。因此全部插入成功，就得到合法前缀码表。

图里把两种顺序分开。第一种是在读完新码字之前遇到A；第二种是在新码字结束的位置看到B仍在下方。红圈都指向真正需要检查的结点，不是泛泛画一棵树。

5. 到达字符后，为什么必须回到根

沿着演示码表译码010110111，可以分为：

0 | 10 | 110 | 111 A | B | C | D

字符在叶子上，意味着不存在更长码字要从这里继续；可以立即保存字符。而下一字符的路径仍然是从根开始定义的，不是从当前叶子延伸，所以必须回根。

下面用红线标出从根读0到A，以及译出A之后回根。B、C、D也是同一个操作；星号结点只是中间路径，不输出字符。

可以把译码不变量理解成：当前指针所在的路径，恰好对应“上一个已完成字符之后，已经读入但尚未组成完整字符的那些位”。保存一个字符并回根后，这段未完成路径重新变为空。

6. 合法码表，不代表每条输入流都合法

译码失败有三种不同原因，不能只检查末尾：

所以需要逐位检查合法位和孩子是否存在，最后检查指针是否回到根。空编码流在合法码表上表示空消息，可以成功；空码字会成为所有码字的前缀，禁止。

还有一个工程选择：01011能先读出A、B，但最后的11是不完整码字。如果边走边putchar，会在报错前已经打印AB。本地程序先存到输出缓冲区，整条流成功后再输出，不把部分结果当成功。真正的流式接口也可以交付部分结果，但必须另外定义它的提交语义。

7. 完整C程序与职责划分

先给完整可编译的C11程序。输入每组是n、n行字符与码字，以及编码流，可连续输入直到EOF。

本地约定2≤n≤26，字符A～Z，码字不超过256位，编码流不超过200000位。-表示空串，x用于测试非法位。重复字符或重复码字视为无效码表。等长的前缀码表也可作为扩展测试，不将其称为原题的不等长样例。

输出分为BOOK_INVALID、STREAM_INVALID、OK ABCD；合法空消息输出OK -。优先检查码表，码表无效时不继续译码。

实现仍是带左右指针的二叉树。为了统一管理内存，所有结点一次申请在连续内存里，孩子指针指向其中的结点。设所有码字总长度为S，每读一位最多新增一个结点，因此预留S+1个结点（包括根）一定够；共享路径会使实际使用量更少。程序用malloc申请结点池，然后显式将两个孩子设为NULL、字符设为'\0'、终止标记设为0。这样不依赖“全零位模式就是空指针”的平台假设；calloc只保证所有位清零。分配失败时程序非正常退出，不把内存不足说成码表非法。

先检查整张码表的字符与位，再修改树，避免非法位导致半条垃圾路径。前缀冲突时丢弃本次整棵树，不继续使用部分建好的结构。统一free结点池也避免了递归释放深树的额外栈开销。

下面的完整程序与本地判题使用的源码一致：

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_CODES 26 #define MAX_CODE_LENGTH 256 #define MAX_STREAM_LENGTH 200000 typedef struct Node { struct Node *child[2]; char ch; int is_char; } Node; typedef struct { char ch; char bits[MAX_CODE_LENGTH + 2]; } Code; typedef struct { Node *nodes; size_t used; } Tree; static int insert_code(Tree *tree, const Code *code) { Node *p = &tree->nodes[0]; for (size_t i = 0; code->bits[i] != '\0'; ++i) { if (p->is_char) return 0; int bit = code->bits[i] - '0'; if (p->child[bit] == NULL) { p->child[bit] = &tree->nodes[tree->used++]; } p = p->child[bit]; } if (p->is_char) return 0; if (p->child[0] != NULL || p->child[1] != NULL) return 0; p->ch = code->ch; p->is_char = 1; return 1; } /* Return -1 for allocation failure, 0 for invalid table, 1 for success. */ static int build_tree(Tree *tree, const Code *codes, size_t count) { size_t capacity = 1; int seen[26] = {0}; tree->nodes = NULL; tree->used = 0; for (size_t i = 0; i < count; ++i) { unsigned int index = (unsigned int)(codes[i].ch - 'A'); if (index >= 26 || seen[index]) return 0; seen[index] = 1; size_t length = strlen(codes[i].bits); if (length == 0 || length > MAX_CODE_LENGTH) return 0; for (size_t j = 0; j < length; ++j) { if (codes[i].bits[j] != '0' && codes[i].bits[j] != '1') return 0; } capacity += length; } /* At most one new node per input bit. */ tree->nodes = malloc(capacity * sizeof(*tree->nodes)); if (tree->nodes == NULL) return -1; for (size_t i = 0; i < capacity; ++i) { tree->nodes[i].child[0] = NULL; tree->nodes[i].child[1] = NULL; tree->nodes[i].ch = '\0'; tree->nodes[i].is_char = 0; } tree->used = 1; for (size_t i = 0; i < count; ++i) { if (!insert_code(tree, &codes[i])) return 0; } return 1; } static int decode(const Node *root, const char *bits, char *out) { const Node *p = root; size_t written = 0; if (strcmp(bits, "-") == 0) { out[0] = '\0'; return 1; } for (size_t i = 0; bits[i] != '\0'; ++i) { if (bits[i] != '0' && bits[i] != '1') return 0; int bit = bits[i] - '0'; if (p->child[bit] == NULL) return 0; p = p->child[bit]; if (p->is_char) { out[written++] = p->ch; p = root; } } if (p != root) return 0; out[written] = '\0'; return 1; } int main(void) { char *bits = malloc(MAX_STREAM_LENGTH + 2); char *out = malloc(MAX_STREAM_LENGTH + 1); if (bits == NULL || out == NULL) { free(bits); free(out); return 1; } int n, status; while ((status = scanf("%d", &n)) != EOF) { if (status != 1 || n < 2 || n > MAX_CODES) { free(bits); free(out); return 1; } Code codes[MAX_CODES]; for (int i = 0; i < n; ++i) { char symbol[3]; if (scanf("%2s%257s", symbol, codes[i].bits) != 2 || strlen(symbol) != 1 || symbol[0] < 'A' || symbol[0] > 'Z' || strlen(codes[i].bits) > MAX_CODE_LENGTH) { free(bits); free(out); return 1; } codes[i].ch = symbol[0]; } if (scanf("%200001s", bits) != 1 || strlen(bits) > MAX_STREAM_LENGTH) { free(bits); free(out); return 1; } Tree tree; int built = build_tree(&tree, codes, (size_t)n); if (built < 0) { free(bits); free(out); return 1; } if (!built) puts("BOOK_INVALID"); else if (!decode(&tree.nodes[0], bits, out)) puts("STREAM_INVALID"); else printf("OK %s\n", out[0] == '\0' ? "-" : out); free(tree.nodes); } free(bits); free(out); return 0; }

可以用GCC编译，然后以文件重定向方式输入多组数据：

gcc -std=c11 -O2 -Wall -Wextra solution.c -o solution ./solution < sample.in

示例输入如下，成功输出为OK ABCD：

4 A 0 B 10 C 110 D 111 010110111

8. 复杂度：不是平衡树，不要写成log n

设码字总位数为S，编码流长度为M，最长码字为L。

建树处理每一位常数次，总时间O(S)。译码每位走一步，并在字符结束时回根，总时间O(M)。单次插入O(码字长度)，最多O(L)，不是按字符数取对数。

树占O(S)空间。若只做即时流式输出，译码本身除树以外只需当前指针等常数状态。这里为了失败时不提交部分结果，需要保存输出；长度至多M，按实际长度分配时需要O(M)空间。

这份C程序为了复用缓冲区，实际一次性按本地流长上限M_max=200000预留输入和输出，因此实现的存储容量是O(S+M_max)，不是随每组实际M缩小，也不能说整份实现只有O(1)空间。

9. 怎样独立验证，而不是再造一棵树

参考解与候选C程序走不同路径。码表合法性直接两两比较字符串：任意两码字中，一个以另一个开头（包含相等），就有冲突；同时检查空码字、非法位和重复字符。

合法码表的参考译码器从当前位置检查各个码字，找到完整匹配就消费对应长度。前缀特性保证同一位置最多匹配一个码字；没有匹配则为无效编码流。它不创建树，也不复用孩子指针或回根状态。

下面是字符串参考解的等价简化版本，可用Node.js直接运行。这里直接以空字符串表示空消息，与本地输入中的-token 区分；输入假定是满足字符数量与长度约定的码表对象。

function checkBook(codes) { if (new Set(codes.map(x => x.ch)).size !== codes.length) return false; if (codes.some(x => !/^[01]+$/.test(x.code))) return false; for (let i = 0; i < codes.length; ++i) for (let j = i + 1; j < codes.length; ++j) if (codes[i].code.startsWith(codes[j].code) || codes[j].code.startsWith(codes[i].code)) return false; return true; } function reference(codes, bits) { if (!checkBook(codes)) return 'BOOK_INVALID'; if (!/^[01]*$/.test(bits)) return 'STREAM_INVALID'; let at = 0, out = ''; while (at < bits.length) { const found = codes.filter(x => bits.startsWith(x.code, at)); if (found.length !== 1) return 'STREAM_INVALID'; out += found[0].ch; at += found[0].code.length; } return 'OK ' + (out || '-'); } const codes = [ { ch: 'A', code: '0' }, { ch: 'B', code: '10' }, { ch: 'C', code: '110' }, { ch: 'D', code: '111' } ]; console.log(reference(codes, '010110111')); // OK ABCD console.log(reference(codes, '01011')); // STREAM_INVALID

测试不仅比较字符串，还检查错误状态：合法码表的残缺流必须输出STREAM_INVALID，不能拿BOOK_INVALID蒙混过关。随机合法码表从叶子不断分裂生成，再随机选择字符、拼接码字；码表逆序不应改变结果。截断末位不一定非法，可能刚好删掉一个长度为1的码字，所以截断测试仍由参考解判定，不预设错误状态。

另外先将码字按字典序排序，检查相邻项的前缀关系，并核对字符是否重复，独立确认码表合法性。对合法码表下的短编码流，用动态规划统计全部完整分割：零种表示无效，一种对应唯一译码结果。这里不以参考解已经判成功为前提，成功流和失败流都会检查，还故意给分割检查传入错误的成功、失败答案，确认两种误判都能被发现。另做“译码后重新编码”的往返检查，候选程序、参考匹配器和分割检查不是同一套逻辑。

判题工具的执行顺序是：先用GCC编译候选C程序，再解析自定义输入或生成测试数据；确认输入符合本地约定后，由独立参考解计算答案，将整批数据输入候选程序，最后逐行检查状态与译码结果。编译失败、非正常退出、超时、答案错误、输入格式错误分别报告CE、RE、TLE、WA、JUDGE_ERROR。失败时保存第一组反例，网页可以直接用它重新测试，不需要手动重构输入。

实际已运行：

穷举范围为长度1～3的全部非空二进制码字，共14个；取两条作为A、B的编码，共14²组有序码表（包含非法表）。编码流长度0～4，共31条，所以测试6076组。这只是明确范围内的穷举，不是一般正确性证明。

大数据覆盖256位码字、26个字符、200000位成功流和长流末尾残缺。两个完整批次有重复用例，不将其数量相加宣称为不同用例。运行超时针对整批程序，不把测得耗时当成纯译码函数的性能；本地工具只适合可信代码，没有公共OJ的系统隔离和内存计量。

10. 最后收回原题的三个小问

第一问：用二叉树保存编码，0/1对应两个分支；每个字符保存在其码字路径的叶子终点。

第二问：从根开始逐位沿分支走，到达字符叶子后译出字符，再回根处理后续位。实现扩展中还检查非法路径与末尾是否完整。

第三问：按码字建树，途中不能经过已保存字符的结点；新码字结束的结点不能已有字符或孩子。全部通过，字符终点互不为祖先且码字不重复，满足前缀特性。

与上一题先化简距离公式不同，这里从定义中找到结构约束：一个字符结束后不能还有另一个字符的路径。真正把程序写出来后，“字符只放在叶子”就不再是一句孤立结论，而是同时约束建树、译码与检查的规则。