# Prüfer 编码图解：删去最小叶子，如何还原一棵树？

用双树 SVG 舞台同步演示最小叶子删除与边的复原。理解邻居序列、剩余次数和度数关系，处理重复元素、最后一条边及 n=2 空序列。

原文 / Canonical: https://crazycloud.cc/learn/prufer-code
作者: crazycloudcc
首次发布: 2026-11-01
更新: 2026-11-01

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

Prüfer 编码每次删去标号最小的叶子，记录它唯一的邻居，共记录 n−2 项。解码时，选尚未处理且未在剩余序列出现的最小标号，把它与当前项相连。消费一项后继续，最后连接剩下两点。

## 适用条件与边界

讨论标号为 0..n−1 的简单无向树，n≥2。交互与本页模型限定 2≤n≤8；输入序列长度恰为 n−2，每项是范围内整数，允许重复。图中的圆周位置只为稳定布局，边的交叉不是额外顶点。n=1 不在此演示范围内。

## 不变量

处理 k 项后，尚未处理顶点的剩余树度数 = 剩余序列中该标号的出现次数 + 1；两边每步使用同一条边，但左图删边、右图添边。

## 逐步例子

1. 原创路径 0—1—2—3：叶子先有 0、3，删 0 记邻居 1；再删 1 记 2，得到 [1,2]，最后边为 2—3。
2. 反向读 [1,2]：初始缺席标号有 0、3，取最小的 0 接到 1；剩 [2]，从活动顶点中取最小缺席标号 1 接到 2；最后接 2—3。
3. 原创五点星形中心为 0：依次删叶 1、2、3，编码为 [0,0,0]，最后剩 0—4。重复不是错误，反而揭示中心的高连接度。
4. 一个活动顶点总会保留一条“最后离开”的边。其余每条相邻边先被叶子删掉时，都会记录它一次，所以剩余度数等于剩余出现次数加一。这个度数属于剩余树，不是右侧已经复原部分的度数。
5. 每次选叶时，剩余序列还包含当前项。选好以后才消费当前项、移除叶子；反过来可能把当前邻居错当成叶子。已处理顶点即使计数为零也不可再次选择。
6. n=2 的编码是空序列，但原树仍有一条边；演示单列“连接最后一条边”操作，不把空序列当作没有树。
7. 每个合法序列都能复原一棵树，再编码得到原序列。因而 n≥2 时，有标号树数量为 n^(n−2)。例如四点共有 4²=16 棵有标号树，并不是 16 种忽略标号的形状。

## 扫描实现与教学轨迹成本

本页使用扫描最小叶子的朴素方法，不是堆或指针优化：单次编码、解码为 O(n²) 时间。解码额外空间 O(n)，矩阵编码空间 O(n²)。教学帧保存每步的边与顶点副本，当前生成方式至多 O(n³) 时间、O(n²) 存储，不能把整套动画轨迹称作 O(n) 空间。交互上限 8 只为可读性，不是 Prüfer 定理的上限。

## 常见误区

- 记录被删的叶子，而非它的邻居
- 按画面最左点选叶，而不是按标号最小
- 序列用完就停止，漏掉最后一条边
- 把剩余度数误当作已复原图的度数
- 删除当前项之后才选择叶子，或重新选择已处理顶点
- 把有标号树数量误认为不区分标号的树形数量

## 自测

n=5 的序列 [0,0,0] 复原哪些边？为什么不是三个顶点？

标号集合是 0..4。依次得到 1—0、2—0、3—0，再补最后的 0—4；序列有 n−2=3 项，不代表树只有 3 个顶点。

## 参考资料

- [AtCoder Algorithm Lectures：Prüfer code（2026-10-30）](https://info.atcoder.jp/entry/algorithm_lectures/prufer_code)

[返回图解实验室](https://crazycloud.cc/learn)