tree - 两棵二叉树同构是什么意思？

Question

两棵二叉树同构是什么意思？我一直在网上寻找，似乎找不到明确的解释。

据我了解，如果两棵树具有相同的形状，它们就是同构的。所以我猜测两个相同的树可以在节点中包含不同的值。

Answer 1

同构来自希腊语“相同的形状”（如等压线是具有相同气压的点，多边形表示“多面”）所以你的理解是正确的。但是不要误以为在这种情况下形状是物理形状（就像树有一个根，一个左节点和一个右节点；请参见下面的示例）。数学家有他们自己的语言，只是有时与英语有短暂的关系:-)

它不仅仅是二叉树。在数学中，两个结构是同构的，如果它们的属性被保留而不考虑它们的表达式（你可以有一个函数将 A 转换为 B，另一个从 B 转换为 A 而不会丢失信息）。

对于您的特定情况，保留的是树中的信息。例如，如果该信息是 sorted elements {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

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

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/

Answer 3

我认为你的理解是非常正确的。如果您忽略这些值并只查看结构，那么对于第一棵树中的每个节点，在另一棵树中都必须有一个对应的节点，反之亦然。

自然，两棵树将具有相同数量的节点。此外，您可以编写一个（超朴素）算法来通过尝试所有可能的映射函数来确认这种同构，并确保对于第一棵树中映射到另一棵树中的节点的每个节点，相应的映射发生在父母和两个孩子。显然有有效的算法来检查这一点。

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