两棵二叉树同构是什么意思? [英] What does it mean for two binary trees to be isomorphic?

问题描述

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

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.

推荐答案

Isomorphic 来自希腊语相同的形状"(就像 isobar 是具有相同气压的点，而多边形的意思是多面")所以你的理解是正确的.但是不要误以为在这种情况下形状是物理形状(例如树有一个根、一个左节点和一个右节点；例如见下文).数学家有自己的语言，只是有时与英语有短暂的关系:-)

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 :-)

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

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).

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

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:

  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):

  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.

这篇关于两棵二叉树同构是什么意思?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！