What does it mean for two binary trees to be isomo

问题:

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.

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

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

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.

回答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 .

2.Two trees are isomorphic if and only if they have same degree spectrum .

3.Two trees are isomorphic if and only if they have same degree of spectrum at each level.

4. 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/

回答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.