Definition. Hille 编码 [hille-encode]
Definition. Hille 编码 [hille-encode]
以下三条规则给出 Hille 编码到二叉树的转换过程. 同时不难验证, 任给一个二叉树, 可以通过这三条规则得到其 Hille 编码.
1
表示添加当前树节点的左子树. 例如111
表示的树为(⋅ (⋅ (⋅)))
.01
表示添加当前树节点的右子树. 例如10101
表示的树为(⋅ _ (⋅ _ (⋅)))
.- 而对于
01
前的 $k$ 个0
, 这些0
用于表示将当前树节点回溯到前 $k$ 层. 例如11001
表示的树为(⋅ (⋅) (⋅))
.
注意到每个树节点的双亲 (parent) 节点是唯一的, 因此回溯操作良定, 一次回溯就是将当前节点改为其双亲.