前序列表告诉我们哪个节点先被访问,但仅有节点值列表未必能反映哪些子节点缺失。例如,仅有左子节点的根与仅有右子节点的根,可能有相同的前序值。为每个空子节点位置加入特殊空标记后,数据流便同时记录了值与结构。
这一推导应用扩展了课程的二叉树遍历与重建单元。
1. 编码与明确格式
二叉树有限且有序:左、右子节点位置不同。值可以重复。用特殊记号 # 表示空子树,并假设它不会与任何编码后的值记号混淆。递归序列化:
encode(node):
如果 node 为空:输出 #;返回
输出 VALUE(node.value)
encode(node.left)
encode(node.right)
VALUE(v) 是带类型标记的值记号,不是可能与 # 混淆的普通字符串。实际格式需要区分两者,即使例子中简写成字母。空树编码为单个记号 #。
定义 4.3.1
(带空标记的前序编码)
对有限有序二叉树 ,其带空标记的前序编码是记号序列 ,定义为 ;对值为 、左子树为 、右子树为 的节点,。第一个记号是根的值或空标记。
例题 4.3.2
(编码缺少左子节点的树)
例如,设 的左子节点为 、右子节点为 ,而 只有右子节点 ; 都是叶节点。编码为
A B # D # # C # #
第一个 # 标记 缺失的左子节点;接下来两个结束 ,最后两个结束 。如果只是把空标记追加到末尾,就无法保留缺失子节点的位置。
反例模式
只有值不能决定树
一个诱人的说法是:前序值列表已足以决定树。取 ,根为 且只有左子节点 ;以及 ,根为 且只有右子节点 。两者的前序值都是 ,却是不同的有序树。加上空标记后, 编码为 A B # # #, 编码为 A # B # #:第一个空标记的位置记录了缺少哪个子节点。补救办法是在每个空子节点位置加入空标记。
2. 每次解码一棵子树
decodeOne(tokens, position):
如果 position == length(tokens):报错「截断」
token = tokens[position]; position += 1
如果 token == #:返回 (null, position)
如果 token 不是有效 VALUE:报错「无效记号」
(left, position) = decodeOne(tokens, position)
(right, position) = decodeOne(tokens, position)
返回 (new node(token.value, left, right), position)
decodeTree(tokens):
(root, position) = decodeOne(tokens, 0)
如果 position != length(tokens):报错「多余记号」
返回 root
decodeOne 恰好消耗一棵完整子树,并返回下一棵子树的起始位置。非空记号首先确定根的值;下一棵完整子树是左子树,再下一棵是右子树。空记号消耗一个位置,不产生子节点。外层检查拒绝完整树之后的多余记号。实际实现若后续解析失败,应释放已分配的节点;上述伪代码规定结果,不规定特定语言的所有权策略。
定理 4.3.3
(解码是编码的逆运算)
对每棵有限有序二叉树 ,decodeTree(encode(T)) 返回形状和值都与 相同的树。反过来,被 decodeTree 接受的每个记号数据流,都恰好是一棵这样的树的编码,即使值重复也成立。
证明
(对树归纳)
对编码树归纳可知,解码器恰好消耗其编码并重建根及两个子节点。反过来,成功解码的子树的第一个记号决定它是否为空,或给出其根值;递归解析唯一决定每个子节点和记号边界。因此,一个有效完整数据流恰好表示一棵有序树,即使节点值重复也成立。
3. 用待填槽位数验证结构
定义 4.3.4
(待填槽位与槽位数)
槽位是等待填入整棵子树的位置。开始时根有一个槽位。每个记号填入一个槽位。空标记不创建新槽位,因此数量减 1;值记号创建两个子槽位,因此净变化为 。遇到无效记号则拒绝。若下一个记号到来之前槽位数已为零,也拒绝;只有恰好在末尾变为零才接受。空数据流的槽位数仍为 1,因此已截断。
定理 4.3.5
(槽位计数恰好接受完整的数据流)
设数据流有 个记号,每个都是 # 或有效的值记号。令 ;若第 个记号是值,则 ,若是 #,则 。则 decodeTree 接受该数据流,当且仅当对每个 有 ,且 。
证明
(槽位即待处理的递归调用)
该条件既必要也充分。在每个前缀处,槽位对应前序递归中尚待调用的子树。值把下一个待调用位置替换成两个调用,左先右后;# 完成一个调用。正槽位数保证下一个记号有位置,末尾为零表示没有待处理调用。因此完整数据流符合递归语法。槽位计数检查结构,每个值记号仍须独立符合其格式。
证明透视
槽位计数保留了什么?
计数记录尚未填入的子树位置有多少;它本身不保存节点值,也不能单独重建树的形状。递归解析还依靠记号次序,先取完整左子树,再取右子树。只有此前没有前缀提前耗尽所有槽位时,末尾为零才能证明数据流完整。
对于含 个真实节点的树,空标记有 个。每个节点有两个子节点位置,共 个;非空树有 条真实子边,所以空子节点位置为 。当 时,根槽位本身给出一个标记。完整数据流有 个记号。仅有这一数量还不够:# A # 有一个值和两个标记,但第一个记号已完成根,后续记号多余。
例题 4.3.6
(沿着编码追踪槽位数)
取编码一节的数据流 A B # D # # C # #。计数从 1 开始,变化如下。
| 记号 | 变化 | 之后的槽位数 |
|---|---|---|
| 开始 | 1 | |
A | +1 | 2 |
B | +1 | 3 |
# | −1 | 2 |
D | +1 | 3 |
# | −1 | 2 |
# | −1 | 1 |
C | +1 | 2 |
# | −1 | 1 |
# | −1 | 0 |
每个记号之前计数都至少为 1,恰好在末尾为 0,所以数据流被接受,与解码器一致。
例题 4.3.7
(边界情形:空树、单个节点与错误数据流)
数据流 # 的计数为 :被接受,解码为空树。数据流 A # # 的计数为 :只有一个没有子节点的节点。数据流 A # 结束时计数为 1,所以解码器在读取右子节点时用尽记号,以“截断”报错。数据流 # A # 在第一个记号之后计数为 0,但仍剩两个记号:decodeOne 在一个记号后返回空树,decodeTree 发现位置 1 不等于长度 3,以“多余记号”报错。
常见错误
(数记号个数而不是数槽位)
记号总数 与空标记数 是必要条件,却不充分。数据流 # A # 有三个记号、一个值和两个空标记,符合 的数量,却不是任何树的编码:第一个空标记已完成整棵树,其余记号是多余的。槽位计数能发现这一点,因为第一个记号之后计数为 0,而记号仍有剩余。
常见错误
(漏掉对多余记号的检查)
若 decodeTree 直接返回 decodeOne 的结果,而不比较 position 与长度,则 # A # 会被静默解码为空树,两个记号被忽略。解析出一棵完整子树,并不等于解析了完整数据流。
4. 代价与限制
定理 4.3.8
(编码、解码与验证的代价)
设树有 个节点、高度为 (根到叶路径上的最大真实节点数,空树的 )。在记号操作为常数时间的模型下,编码与解码各需 时间,输出或输入含 个记号。递归栈使用 空间,链状树为 。只用槽位计数验证需要 时间和 个范围足够的计数器(不计输入存储),并且不构造树。
证明
(每步一个记号)
编码器每次调用输出一个记号,恰好调用 次:每个节点一次,每个空子节点位置一次。解码器每次调用至少消耗一个记号,每个记号对应一次调用。递归深度至多比高度多一。验证器只读取每个记号一次,并保持一个计数器。
这些界假设值符合常数时间记号模型;复制可变长度的值还需计入其总长度。带空标记的前序是不同于普通前序的表示,特殊标记和完整数据流验证都是约定的一部分。
5. 习题与解答
快速检查
(编码这棵树:根 只有左子节点 ,而 是叶节点。)
先写 ,再写左子树,最后写右子树。
解答 · 答案
X Y # # #。根 之后是其左子树的编码 Y # #,然后是空右子树的空标记 #。
快速检查
(A # B # # 能否解码?得到哪棵树?用槽位数检查。)
逐个记号追踪计数。
解答 · 答案
计数为 ,每个记号之前都为正,末尾为零。它解码为:根 的左子树为空,右子节点 是叶节点。
快速检查
(含 7 个节点的树,其编码有多少个记号、多少个空标记?)
使用 与 这两个数量。
解答 · 答案
共 个记号,其中 个是空标记,7 个是值。