Was bedeutet es für zwei binäre Bäume bedeuten isomorph zu sein?

Question

Was bedeutet es für zwei binäre Bäume bedeuten isomorph werden? Ich habe Online gesucht und ich kann nicht eine klare Erklärung zu finden scheinen.

Soweit ich verstehe, zwei Bäume sind isomorph, wenn sie die gleiche Form haben. Also vermute ich, zwei identische Bäume, die unterschiedlichen Werte in dem Knoten enthalten kann.

Answer 1

Isomorphische kommt aus dem Griechischen „gleiche Form“ (wie isobar sind, Punkte mit dem gleichen Luftdruck und Polygon bedeutet „vielseitige“), damit Ihr Verständnis korrekt ist. Aber machen Sie nicht den Fehler, in diesem Fall Form unter der Annahme ist eine physische Form (wie der Baum hat eine Wurzel, einen linken Knoten und einen rechten Knoten, siehe unten zum Beispiel). Mathematiker haben ihre eigene Sprache, die nur manchmal eine vorübergehende Beziehung zu Englisch trägt: -)

Es ist nicht nur binäre Bäume. In der Mathematik zwei Strukturen sind isomorph, wenn ihre Eigenschaften unabhängig von ihrem Ausdruck erhalten sind (Sie können eine Funktion haben, die ohne Informationsverlust A nach B und einem weiteren von B nach A übersetzt).

Für Ihren speziellen Fall ist es die Informationen, die in dem Baum, die erhalten wird. Zum Beispiel, wenn diese Informationen die sortierten Elemente {1,2,3} ist, dann ist der Baum muss nicht gleich sein physischen Form überhaupt - die beiden folgenden wäre isomorph:

  2      1
 / \      \
1   3      2
            \
             3

A sortiert verknüpften Liste (oder sortiertes Array, was das betrifft) auch isomorph zu denen, da in diesem Fall würden keine Informationen in den Transformationen zwischen den beiden verloren.

Wenn der binäre Baum wurde in einer Weise verwendet, in denen Sortierreihenfolge irrelevant war (dh eine „Tasche“ Art Container), dann würde die Informationen nur den Inhalt in beliebiger Reihenfolge angegeben werden, und alle folgenden wäre isomorph (das zweite letzte ist nur ein Beutel, der letzte ist eine Liste):

  2      1           2   3                   +---+  +---+  +---+
 / \      \         /     \      +-------+   | 3 |->| 1 |->| 2 |
1   3      2       1       2     | 1,3,2 |   +---+  +---+  +---+
            \     /         \    +-------+
             3   3           1

Natürlich ein unsortierter Baum betrachtet werden kann ein bisschen eine Verschwendung je nach Ihren Bedürfnissen zu sein, aber das ist nicht relevant für diese besondere Diskussion.

Answer 2

Folgende Bedingungen müssen zwei Bäume erfüllen isomorph sein:
1. Zwei Baum ist isomorph, wenn und nur wenn sie in jeder Ebene gleiche Anzahl der Ebenen und gleichen nicht von Eckpunkten erhalten.

2.Two Bäume sind isomorph, wenn und nur wenn sie denselben Grad-Spektrum haben.

3.Two Bäume sind isomorph, wenn und nur wenn sie auf jeder Ebene gleichen Grad an Spektrum aufweisen.

4. Total kein Blatt Nachkomme eines Scheitels und der Ebene Anzahl der Vertex sind beide Baum Baum isomorph invariant.

In einfachen Worten:
Zwei Bäume sind isomorph, wenn ein Baum kann von anderen erhalten werden, indem eine beliebige Anzahl von Flips Durchführung d.h links childrens Swapping und rechts der Kinder aus einer Anzahl von Knoten.

Beispiel von isomorph Bäume:

Ref: 1. http://www14.in.tum.de/konferenzen/ Jass03 / Präsentationen / eterevsky.pdf 2. http://www.geeksforgeeks.org/tree-isomorphism-problem/

Answer 3

Ich denke, Ihr Verständnis ziemlich korrekt ist. Wenn Sie die Werte ignorieren und nur Blick auf die Struktur, die dann für jeden Knoten im ersten Baum muss es einen entsprechenden Knoten im anderen Baum sein und umgekehrt.

Natürlich müßten beide Bäume die gleiche Anzahl von Knoten. Darüber hinaus können Sie einen (Super-naiv) Algorithmus schreiben, um diesen Isomorphismus zu bestätigen, indem alle möglichen Abbildungsfunktionen versuchen, und dass in dem ersten Baum für jeden Knoten zu gewährleisten, die einen Knoten in den anderen abgebildet wird, ist nun mal die entsprechende Abbildung mit der Eltern und mit den beiden Kindern. Natürlich gibt es effiziente Algorithmen für diese zu überprüfen.

Sie profitieren von der Lektüre über Graphisomorphie zuerst; Bäume sind ein spezieller (und leichter zu lösen) Fall, da sie Zyklen nicht haben.