Appearance
2020·42 前缀编码译码：把「字符只放叶结点」这条约束用透
本文属于「从暴力解到最优解」专题的第二组。这道题跟「算法快不快」完全无关——它是一道数据结构设计题，考的是能不能从一句抽象定义（前缀特性）反推出唯一合适的数据结构，以及能不能把由此衍生出的每一个操作过程讲全。设计题考的是判断力，不比复杂度。
题目
任一个字符的编码都不是其它字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数 ≥ 2）的不等长编码，每个字符的编码均为二进制的 0、1 序列，最长为 L 位，且具有前缀特性。请回答下列问题：
(1) 哪种数据结构适宜保存上述具有前缀特性的不等长编码？
(2) 基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程。
(3) 简述判定某字符集的不等长编码是否具有前缀特性的过程。
总分 8 分。这道题没有「尽可能高效」这层要求，因为它压根不比复杂度——三问考的是选型、流程、判定逻辑三种不同的设计能力，答案对不对全看有没有把关键约束用透，不看代码跑得多快。
关键在「字符全放叶结点」这个设计
三问的答案其实是一条线串起来的：第一问选出的数据结构，直接决定了第二问和第三问的做法。而这个数据结构的核心设计，就是把每个字符绑定到一个叶结点上，内部结点只负责分叉、不存字符。
为什么这样设计天然就满足前缀特性？关键在于"叶结点"在树里的位置——叶结点永远是某条根到叶路径的终点，不会出现在另一条路径的中间。把这句话翻译成编码语言：每个字符的编码就是「根到它所在叶结点」这条路径上的 0/1 序列；如果字符 A 的编码是字符 B 编码的前缀，就意味着从根走到 A 的这条路径，恰好是走到 B 的路径的一段前缀——也就是说，B 的路径上会"路过" A 所在的那个结点。但 A 是叶结点，叶结点没有子结点，任何路径都不可能"路过"它再往下走。所以只要字符都在叶结点上，前缀特性就是这棵树结构自带的性质，不需要额外验证。
反过来看，如果字符也允许存在内部结点会怎样：假设字符 A 存在一个既有子结点又代表 A 的内部结点，那么从根到 A 的路径，恰好是从根到 A 的任意一个后代叶结点路径的前缀——前缀特性直接被破坏。这就是为什么「字符全在叶结点」是这道题唯一正确的设计——它是前缀特性逼出来的必然选择。
三问逐一作答
(1) 数据结构：二叉树（前缀码 trie / 编码树）
构造规则三条：
- 每个字符存放在一个叶结点——根到该叶结点的 0/1 路径就是该字符的编码；
- 内部结点不存字符——只起路径分叉的作用；
- 左分支记 0，右分支记 1（约定即可，反过来也行）。
树最多有
编者注（生僻术语）：哈夫曼树（Huffman tree）就是这种"编码树"的一种特殊构造——按字符出现频率构造，使加权路径长度最短，从而让整体编码长度最优。本题不要求最优编码，任何"字符全在叶结点"的二叉树都满足前缀特性，哈夫曼树只是这类树里频率意义上最优的一个特例。
(2) 译码过程：从根按位走，遇叶输出并回根
从根出发，按位读入 0/1 串：0 走左孩子，1 走右孩子；一旦走到叶结点，就输出该叶结点绑定的字符，然后把当前位置重新拨回根，继续读下一位。如此循环，直到 0/1 串读完。
text
cur ← 根
result ← 空字符串
对 0/1 串中每一位 b：
若 b = 0：cur ← cur.left
否则： cur ← cur.right
若 cur 是叶子：
result ← result + cur.char
cur ← 根 // 回到根，准备下一个字符
返回 result这个过程之所以走得通、不会有歧义，靠的正是第一问确立的前缀特性：每次到达叶结点的时刻是唯一确定的——不会出现"这里已经是一个字符的编码了，但还得往下走看看是不是别的字符编码的前缀"这种犹豫。如果读完整个 0/1 串时 cur 还没落在根上（说明最后一段路径走了一半没到叶结点），说明这串 0/1 本身不是合法编码。时间复杂度是
(3) 前缀性判定：逐条插入编码树，看有没有"撞"上已有结点
给一组编码（还不确定是否具有前缀特性），怎么检验？做法是把每个编码依次当作一条 0/1 路径插入一棵空二叉树，边插边检查有没有出现下面两种"撞车"情况，出现任意一种就判定不具备前缀特性；全部插完都没出现，就具备。
text
建一棵只有根的空树
对每个字符的编码 code：
cur ← 根
对 code 中每一位 b：
若 cur 已被标记为叶子：返回 "不具备前缀特性" // 情况 1
若 cur 沿 b 方向无孩子：建该孩子
cur ← cur 沿 b 方向的孩子
若 cur 已有孩子：返回 "不具备前缀特性" // 情况 2
把 cur 标记为叶子（绑定到当前字符）
返回 "具备前缀特性"两种违反情况一定要都答到，它们分别对应前缀关系的两个方向：
- 情况 1：插入新编码的过程中，途中经过了一个已经被标记为叶结点的位置。 这说明有一个更短的编码（那个已有的叶结点）恰好是当前这个新编码的前缀——老码是新码的前缀。
- 情况 2：新编码插完最后一位、准备把当前结点标为新叶结点时，发现这个结点已经有孩子了。 有孩子意味着已经有别的更长编码从这里继续往下走，也就是说当前这个新编码，反过来是某个已有编码的前缀——新码是老码的前缀。
这两种情况方向相反，但都是"前缀关系"的体现，判定逻辑必须两个都覆盖，只答一半是不完整的判定。复杂度是
编码树长什么样，看一遍
下面的交互演示是一棵按频率构造的哈夫曼树——它是"字符全在叶结点"这类编码树里的一个具体例子，可以直观感受叶结点、内部分叉结点，以及从根到叶的路径如何对应一份编码：
常见错点
- 把字符存进内部结点。 这是本题最致命的错误——一旦某个字符挂在内部结点上，前缀特性直接被破坏，第一问的设计就站不住脚，第二、三问的译码和判定过程也会跟着失效。
- 判定前缀性时只说一种违反情况。 比如只讲"途中穿过已有叶子"，漏掉"新叶位置已有孩子"，或者反过来；两种情况分别对应前缀关系的两个方向，必须都提到。
- 译码过程漏说"回到根"。 输出一个字符之后不把
cur拨回根，会导致下一个字符的译码从错误的位置开始。 - 把"前缀特性判定"简化成"看编码长度"。 长度不同不代表没有前缀关系（短的完全可能是长的前缀），必须真正按位比较或走一遍编码树插入过程。
下一步
- 在 OJ 上验证你的思路：ds-2020-42 前缀编码译码
- 回到题库看这道题的完整解析：真题库 · 数据结构