两个二叉树同构意味着什么？

Question

两个二叉树何谓同构？我在网上找了很久，似乎没有清晰的解释。

据我所知，如果两个树的形状相同，则它们是同构的。因此，我猜测两个节点可以包含不同的值，但它们的结构相同。

- user69514

Answer 1

"同形"这个词源于希腊语，意为与“等压线”类似（isobar），或者是“多边形”（polygon），所以你的理解是正确的。但是不要犯将这里的“形状”误认为是指实际的物理形状的错误（比如一棵树有一个根节点、一个左子节点和一个右子节点；可以参考下面的例子）。数学家有自己的语言，有时与英语只有一点关系 :-)

这不仅仅适用于二叉树。在数学中，如果两个结构的属性无论如何表示都保持不变（你可以有一个函数将A转换为B，另一个函数将B转换为A，而不会丢失信息），那么它们就是同构的。

对于您的特定情况，保留的是树中的信息。例如，如果该信息是排序后的元素{1,2,3}，那么树的实际形状可以完全不同 - 下面的这两个树就是同构的：

  2      1
 / \      \
1   3      2
            \
             3

一个已排序的链表(或排序数组)也同构于它们，因为在这种情况下，在两者之间的转换中不会丢失任何信息。

如果二叉树被用于无序排序的方式(比如一个“包”式的容器)，那么信息只是以任意顺序排列的内容，并且以下所有内容都是同构的(倒数第二个只是一个包，最后一个是一个列表):

  2      1           2   3                   +---+  +---+  +---+
 / \      \         /     \      +-------+   | 3 |->| 1 |->| 2 |
1   3      2       1       2     | 1,3,2 |   +---+  +---+  +---+
            \     /         \    +-------+
             3   3           1

当然，根据您的需求，未排序的树可能被认为有点浪费，但这与本次讨论无关。

- paxdiablo

Answer 2

以下条件必须满足才能使两棵树同构：
1. 仅当两棵树保持相同的层数和每个级别中相同的顶点数时，它们才是同构的。

2. 当且仅当两棵树具有相同的度频谱时，它们是同构的。

3. 当且仅当它们在每个级别上的频谱度相同时，两棵树是同构的。

4. 对于一个顶点的叶子后代总数和顶点的级别编号，这两个属性都是树同构不变量。

简单来说，如果一棵树可以通过交换一些节点的左右孩子来获得另一棵树，则这两棵树是同构的。

同构树的示例： 参考资料： 1.http://www14.in.tum.de/konferenzen/Jass03/presentations/eterevsky.pdf 2.http://www.geeksforgeeks.org/tree-isomorphism-problem/

- igauravsehrawat

---

我认为该定义不正确，除非“同构”在树和图之间的含义不同。即使是这样，我也不确定如何定义同态，或者你的同构定义如何推广到n元树。考虑高度为3且有3个节点的二叉树，以及另一个高度为2且有3个节点的二叉树。两者之间存在同构，但你提供的定义将它们排除在同构之外。 - Iain

Answer 3

我认为你的理解基本上是正确的。如果忽略值，只看结构，那么第一棵树中的每个节点必须有一个对应的节点在另一棵树中，反之亦然。

当然，两棵树将具有相同数量的节点。 此外，您可以编写（超级幼稚的）算法来确认这种同构性，方法是尝试所有可能的映射函数，并确保对于第一棵树中映射到另一棵树中的每个节点，相应的映射发生在父节点和两个子节点之间。 显然有有效的算法来检查这一点。

您可能会从先阅读图同构中受益；树是一个特殊的（更容易解决）情况，因为它们没有循环。

- Uri