What does it mean for two binary trees to be isomorphic? I've been looking online and I can't seem to find a clear explanation.
两个二叉树是同构的意味着什么?我一直在网上看,我似乎无法找到明确的解释。
As far as I understand, two trees are isomorphic if they have the same shape. So I'm guessing two identical trees which can contain different values in the nodes.
据我所知,如果它们具有相同的形状,则两棵树是同构的。所以我猜两个相同的树,它们可以在节点中包含不同的值。
3 个解决方案
#1
Isomorphic comes from the Greek "same shape" (like isobar is points with the same air pressure and polygon means "many sided") so your understanding is correct. But don't make the mistake of assuming shape in this case is a physical shape (like the tree has one root, one left node and one right node; see below for example). Mathematicians have their own language which only sometimes bears a passing relationship to English :-)
同构来自希腊语“相同的形状”(就像isobar是具有相同气压的点和多边形意味着“多边形”)所以你的理解是正确的。但是,在这种情况下,不要假设形状的错误是物理形状(如树有一个根,一个左节点和一个右节点;例如见下文)。数学家有他们自己的语言,有时只与英语有关系:-)
It's not just binary trees. In mathematics, two structures are isomorphic if their properties are preserved regardless of their expression (you can have a function that translates A to B and another from B to A without loss of information).
它不仅仅是二叉树。在数学中,两个结构是同构的,如果它们的属性被保留而不管它们的表达(你可以有一个函数将A转换为B而另一个从B转换为A而不丢失信息)。
For your particular case, it's the information in the tree that's preserved. For example, if that information is the sorted elements {1,2,3}, then the tree doesn't have to be the same physical shape at all - the following two would be isomorphic:
对于您的特定情况,它是树中保留的信息。例如,如果该信息是已排序的元素{1,2,3},那么树根本不必是相同的物理形状 - 以下两个将是同构的:
2 1
/ \ \
1 3 2
\
3
A sorted linked list (or sorted array, for that matter) is also isomorphic to those since, in that case, no information would be lost in the transformations between the two.
排序链表(或排序数组,对于那个问题)也与那些同构,因为在这种情况下,两者之间的转换中不会丢失任何信息。
If the binary tree was used in a manner where sort order was irrelevant (i.e., a "bag" sort of container), then the information would just be the contents in any order, and all the following would be isomorphic (that second last one's just a bag, the last is a list):
如果二进制树以排序顺序无关的方式使用(即,“bag”类型的容器),那么信息将只是任何顺序的内容,并且以下所有内容将是同构的(第二个最后一个)只是一个包,最后是一个列表):
2 1 2 3 +---+ +---+ +---+
/ \ \ / \ +-------+ | 3 |->| 1 |->| 2 |
1 3 2 1 2 | 1,3,2 | +---+ +---+ +---+
\ / \ +-------+
3 3 1
Of course, an unsorted tree may be considered to be a bit of a waste depending on your needs, but that's not relevant to this particular discussion.
当然,根据您的需要,未排序的树可能会被视为有点浪费,但这与此特定讨论无关。
#2
Following conditions must fulfill to two trees to be isomorphic :
1. Two Tree are isomorphic if and only if they preserve same no of levels and same no of vertices in each level .
以下条件必须满足两棵树同构:1。两个树是同构的,当且仅当它们在每个级别中保留相同的no级别和相同的no顶点时才是同构的。
2.Two trees are isomorphic if and only if they have same degree spectrum .
2.当且仅当它们具有相同的光谱度时,两棵树是同构的。
3.Two trees are isomorphic if and only if they have same degree of spectrum at each level.
3.当且仅当它们在每个级别具有相同程度的光谱时,两个树是同构的。
- Total no of leaf descendant of a vertex and the level number of vertex are both tree tree isomorphic invariant .
顶点的叶子后代的总数和顶点的级别数都是树形同构不变量。
IN Simple words :
Two trees are isomorphic if one tree can be obtained from other by performing any number of flips i.e swapping left childrens and right childrens of a number of node .
简单说明:如果一棵树可以通过执行任意数量的翻转从另一棵树获得,即交换左边儿童和多个节点的右子节点,则两棵树是同构的。
Example of isomorphic trees: 
同构树的例子:
Ref: 1.http://www14.in.tum.de/konferenzen/Jass03/presentations/eterevsky.pdf 2.http://www.geeksforgeeks.org/tree-isomorphism-problem/
参考:1.http://www14.in.tum.de/konferenzen/Jass03/presentations/eterevsky.pdf 2.http://www.geeksforgeeks.org/tree-isomorphism-problem/
#3
I think your understanding is pretty much correct. If you ignore the values and just look at the structure, then for every node in the first tree there must be a corresponding node in the other tree and vice versa.
我认为你的理解非常正确。如果忽略这些值并只查看结构,那么对于第一个树中的每个节点,在另一个树中必须有相应的节点,反之亦然。
Naturally, both trees would have the same number of nodes. In addition, you could write a (super-naive) algorithm to confirm this isomorphism by attempting all possible mapping functions, and ensuring that for every node in the first tree that gets mapped to a node in the other, the corresponding mapping happens with the parent and with the two children. There are obviously efficient algorithms to check for this.
当然,两棵树都有相同数量的节点。此外,您可以编写一个(超级天真)算法来通过尝试所有可能的映射函数来确认这种同构,并确保第一个树中的每个节点都映射到另一个节点中的节点,相应的映射发生在父母和两个孩子。有明显有效的算法来检查这一点。
You may benefit from reading about graph isomorphism first; trees are a special (and easier to solve) case since they do not have cycles.
您可以先阅读有关图同构的内容,树是一种特殊的(并且更容易解决)的情况,因为它们没有周期。
#1
Isomorphic comes from the Greek "same shape" (like isobar is points with the same air pressure and polygon means "many sided") so your understanding is correct. But don't make the mistake of assuming shape in this case is a physical shape (like the tree has one root, one left node and one right node; see below for example). Mathematicians have their own language which only sometimes bears a passing relationship to English :-)
同构来自希腊语“相同的形状”(就像isobar是具有相同气压的点和多边形意味着“多边形”)所以你的理解是正确的。但是,在这种情况下,不要假设形状的错误是物理形状(如树有一个根,一个左节点和一个右节点;例如见下文)。数学家有他们自己的语言,有时只与英语有关系:-)
It's not just binary trees. In mathematics, two structures are isomorphic if their properties are preserved regardless of their expression (you can have a function that translates A to B and another from B to A without loss of information).
它不仅仅是二叉树。在数学中,两个结构是同构的,如果它们的属性被保留而不管它们的表达(你可以有一个函数将A转换为B而另一个从B转换为A而不丢失信息)。
For your particular case, it's the information in the tree that's preserved. For example, if that information is the sorted elements {1,2,3}, then the tree doesn't have to be the same physical shape at all - the following two would be isomorphic:
对于您的特定情况,它是树中保留的信息。例如,如果该信息是已排序的元素{1,2,3},那么树根本不必是相同的物理形状 - 以下两个将是同构的:
2 1
/ \ \
1 3 2
\
3
A sorted linked list (or sorted array, for that matter) is also isomorphic to those since, in that case, no information would be lost in the transformations between the two.
排序链表(或排序数组,对于那个问题)也与那些同构,因为在这种情况下,两者之间的转换中不会丢失任何信息。
If the binary tree was used in a manner where sort order was irrelevant (i.e., a "bag" sort of container), then the information would just be the contents in any order, and all the following would be isomorphic (that second last one's just a bag, the last is a list):
如果二进制树以排序顺序无关的方式使用(即,“bag”类型的容器),那么信息将只是任何顺序的内容,并且以下所有内容将是同构的(第二个最后一个)只是一个包,最后是一个列表):
2 1 2 3 +---+ +---+ +---+
/ \ \ / \ +-------+ | 3 |->| 1 |->| 2 |
1 3 2 1 2 | 1,3,2 | +---+ +---+ +---+
\ / \ +-------+
3 3 1
Of course, an unsorted tree may be considered to be a bit of a waste depending on your needs, but that's not relevant to this particular discussion.
当然,根据您的需要,未排序的树可能会被视为有点浪费,但这与此特定讨论无关。
#2
Following conditions must fulfill to two trees to be isomorphic :
1. Two Tree are isomorphic if and only if they preserve same no of levels and same no of vertices in each level .
以下条件必须满足两棵树同构:1。两个树是同构的,当且仅当它们在每个级别中保留相同的no级别和相同的no顶点时才是同构的。
2.Two trees are isomorphic if and only if they have same degree spectrum .
2.当且仅当它们具有相同的光谱度时,两棵树是同构的。
3.Two trees are isomorphic if and only if they have same degree of spectrum at each level.
3.当且仅当它们在每个级别具有相同程度的光谱时,两个树是同构的。
- Total no of leaf descendant of a vertex and the level number of vertex are both tree tree isomorphic invariant .
顶点的叶子后代的总数和顶点的级别数都是树形同构不变量。
IN Simple words :
Two trees are isomorphic if one tree can be obtained from other by performing any number of flips i.e swapping left childrens and right childrens of a number of node .
简单说明:如果一棵树可以通过执行任意数量的翻转从另一棵树获得,即交换左边儿童和多个节点的右子节点,则两棵树是同构的。
Example of isomorphic trees:
同构树的例子:
Ref: 1.http://www14.in.tum.de/konferenzen/Jass03/presentations/eterevsky.pdf 2.http://www.geeksforgeeks.org/tree-isomorphism-problem/
参考:1.http://www14.in.tum.de/konferenzen/Jass03/presentations/eterevsky.pdf 2.http://www.geeksforgeeks.org/tree-isomorphism-problem/
#3
I think your understanding is pretty much correct. If you ignore the values and just look at the structure, then for every node in the first tree there must be a corresponding node in the other tree and vice versa.
我认为你的理解非常正确。如果忽略这些值并只查看结构,那么对于第一个树中的每个节点,在另一个树中必须有相应的节点,反之亦然。
Naturally, both trees would have the same number of nodes. In addition, you could write a (super-naive) algorithm to confirm this isomorphism by attempting all possible mapping functions, and ensuring that for every node in the first tree that gets mapped to a node in the other, the corresponding mapping happens with the parent and with the two children. There are obviously efficient algorithms to check for this.
当然,两棵树都有相同数量的节点。此外,您可以编写一个(超级天真)算法来通过尝试所有可能的映射函数来确认这种同构,并确保第一个树中的每个节点都映射到另一个节点中的节点,相应的映射发生在父母和两个孩子。有明显有效的算法来检查这一点。
You may benefit from reading about graph isomorphism first; trees are a special (and easier to solve) case since they do not have cycles.
您可以先阅读有关图同构的内容,树是一种特殊的(并且更容易解决)的情况,因为它们没有周期。