两个二叉树同构是什么意思? [英] 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.

推荐答案

同构来自希腊语相同的形状"(例如等压线是具有相同气压的点，多边形表示多面")，因此您的理解是正确的.但是在这种情况下，不要误以为形状是 physical 形状(例如树有一个根，一个左节点和一个右节点；例如，请参见下文).数学家有自己的语言，只有有时与英语具有传递性的关系:-)

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}，则树完全不必具有相同的 physical 形状-以下两个将是同构的:

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屋！