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

Question

两个二叉树是同构的意味着什么？我一直在网上看,我似乎无法找到明确的解释.

据我所知,如果它们具有相同的形状,则两棵树是同构的.所以我猜两个相同的树,它们可以在节点中包含不同的值.

Answer 1

同构来自希腊语"相同的形状"(就像isobar是具有相同气压的点和多边形意味着"多边形")所以你的理解是正确的.但是,在这种情况下,不要假设形状的错误是物理形状(如树有一个根,一个左节点和一个右节点;例如见下文).数学家有他们自己的语言,有时只与英语有关系:-)

它不仅仅是二叉树.在数学中,如果两个结构的属性被保留而不管它们的表达如何,则它们是同构的(你可以有一个将A转换为B而另一个从B转换为A而不丢失信息的函数).

对于您的特定情况,它是树中保留的信息.例如,如果该信息是已排序的元素{1,2,3},那么树根本不必具有相同的物理形状 - 以下两个将是同构的:

  2      1
 / \      \
1   3      2
            \
             3

对于那些已排序的链表(或排序的数组)也是同构的,因为在这种情况下,在两者之间的转换中不会丢失任何信息.

如果二进制树以排序顺序无关的方式使用(即,"bag"类型的容器),那么信息将只是任何顺序的内容,并且以下所有内容将是同构的(第二个最后一个)只是一个包,最后是一个列表):

  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/