1.1. 什么是树的同构？
树的同构（Tree Isomorphism）是图同构的一种特殊情况。因为树是无环连通图，所以判断两个树是否同构，本质上是在判断它们是否具有相同的结构。
举个直观的例子：两个树虽然节点名称不同，但它们的父子关系、层级结构、分支形态完全一致。此时我们称这两个树是同构的。
要证明两个树是否同构，可以通过重新绘制其中一个树的结构，使其与另一个完全一致。但这手动操作并不总是容易的，因此我们需要一个高效的算法和形式化定义。
✅ 同构的数学定义
设两个树为：
- $ T_1 = (V_1, E_1) $
- $ T_2 = (V_2, E_2) $
其中：
- $ V_1, V_2 $：树的节点集合
- $ E_1, E_2 $：树的边集合
若存在一个双射函数 $ f: V_1 \rightarrow V_2 $，使得任意两个节点 $ u, v \in V_1 $ 在 $ T_1 $ 中相邻 当且仅当 它们在 $ T_2 $ 中也相邻，即：
$$ (u, v) \in E_1 \iff (f(u), f(v)) \in E_2 $$
则称 $ T_1 $ 和 $ T_2 $ 是同构的，函数 $ f $ 称为它们的同构映射。
1.2. 树结构的编码（Encoding）
为了判断两个树是否同构，我们可以对每个树进行编码（Encoding），使得只有结构相同的树才会有相同的编码。
✅ AHU 编码（Aho-Hopcroft-Ullman）
AHU 编码是一种基于子树结构的递归编码方法。其核心思想是：
- 如果节点是叶子节点，则编码为
0。 - 如果节点是非叶子节点，则将其子节点的编码按升序排列，然后用括号包裹起来作为该节点的编码。
举个例子：
A
/|\
B C D
|
E
该树的 AHU 编码如下：
- 叶子节点 B、C、E 的编码是
0 - D 的子节点只有一个 E，所以编码是
(0) - A 的子节点是 B、C、D，它们的编码分别是
0、0、(0)，排序后是0,0,(0)，所以 A 的编码是(0)(0)(0)
最终，整棵树的编码为 (0)(0)(0)。
1.3. 算法实现（伪代码）
algorithm AHUEncoding(T):
// 输入：一棵树 T
// 输出：该树的 AHU 编码
D <- 构建字典，记录每一层的节点（根节点为第 1 层）
for u in D[h]: // h 是树的高度
AHU(u) <- '0'
k <- h - 1
while k >= 1:
for u in D[k]:
if u 是叶子节点:
AHU(u) <- '0'
else:
AHU(u) <- '(' + 将 u 的子节点的 AHU 编码按升序排列 + ')'
k <- k - 1
return AHU(T.root)
1.4. 同构检测算法
⚠️ 问题：根节点不同怎么办？
两个同构的树如果根节点不同，它们的 AHU 编码可能不同。例如：
A B
/ \ / \
B C A C
这两个树结构相同，但根节点不同，AHU 编码会不同。
✅ 解决方案：使用树的“中心”作为根
树的中心（Center）是指树中最短路径的中点节点。树的中心最多有两个。
我们对两个树分别找出它们的中心，并尝试以这些中心为根进行 AHU 编码比较。
algorithm CheckIsomorphicTrees(T1, T2):
// 输入：两个树 T1 和 T2
// 输出：是否同构
for center1 in FIND-CENTERS(T1):
T1.root <- center1
for center2 in FIND-CENTERS(T2):
T2.root <- center2
if AHU(T1) == AHU(T2):
return true
return false
1.5. 优化版本（按层级比较）
我们可以进一步优化这个算法，通过按层级比较 AHU 编码，一旦发现某一层不匹配，就提前终止比较。
algorithm FasterIsomorphismCheck(T1, T2):
for center1 in FIND-CENTERS(T1):
T1.root <- center1
for center2 in FIND-CENTERS(T2):
T2.root <- center2
D1 <- 构建 T1 的层级节点字典
D2 <- 构建 T2 的层级节点字典
if T1 的高度 != T2 的高度:
return false
h <- T1 的高度
for u in D1[h] + D2[h]:
AHU(u) <- 0
k <- h - 1
while k >= 1:
L1 <- 对 T1 第 k 层节点的 AHU 编码排序
L2 <- 对 T2 第 k 层节点的 AHU 编码排序
if L1 != L2:
return false
k <- k - 1
return true
return false
1.6. 时间复杂度分析
- 每个节点仅被处理一次，时间复杂度为 $ O(n) $
- 每次排序操作的节点数量固定，不随 $ n $ 增长，因此排序的总时间复杂度为 $ O(h) $，其中 $ h $ 是树的高度
- 最坏情况下，两个树各有两个中心，需要比较最多 4 次
✅ 最终时间复杂度为 $ O(n) $
1.7. 小结
- 树的同构意味着它们具有相同的结构
- 可以使用 AHU 编码来表示树的结构
- 通过以树的中心为根进行编码比较，可以高效判断两个树是否同构
- 优化算法可以在层级上提前终止比较，提升效率
- 整体时间复杂度为线性 $ O(n) $，适合大规模树结构比较
📌 常见术语对照表
| 英文术语 | 中文术语 | 备注 |
|---|---|---|
| isomorphism | 同构 | |
| tree | 树 | |
| node | 节点 | |
| leaf node | 叶子节点 | |
| encoding | 编码 | |
| AHU encoding | AHU 编码 | Aho-Hopcroft-Ullman 编码算法 |
| center | 中心 | 树中最短路径的中点节点 |