Bestimmen Sie, ob zwei binäre Bäume gleich sind

Es ist ein kleineres Problem, aber ich würde die Anpassung der früheren Lösung wie folgt aus...

eq(t1, t2) =
  t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)

Der Grund dafür ist, dass Abweichungen sind wahrscheinlich üblich sein, und es ist besser zu erkennen (und aufhören zu vergleichen) früh - vor recursing weiter. Natürlich gehe ich davon aus, dass ein Kurzschluss && operator hier.

Ich werde auch darauf hinweisen, dass dies gern über einige Probleme mit der Handhabung von strukturell verschiedenen Bäume richtig, und mit Ende der Rekursion. Grundsätzlich gibt es einige null-checks für t1.Links etc. Wenn ein Baum hat den Wert null .Links, aber der andere nicht, finden Sie einen strukturellen Unterschied. Wenn beide null .Links, da ist kein Unterschied, aber Sie haben erreicht, ein Blatt - nicht recurse weiter. Nur wenn beide .Links Werte ungleich null haben Sie Durchlaufen, um zu überprüfen Teilbaum. Das gleiche gilt, natürlich, für .Recht.

Man könnte auch überprüft werden, z.B. (t1.Links == t2.Links), aber das macht nur Sinn, wenn Teilbäume werden können physisch geteilt (gleiche Daten-Struktur-Knoten) für die beiden Bäume. Diese Prüfung wäre ein weiterer Weg, um zu vermeiden, recursing, wo es unnötig ist - wenn t1.Links und t2.Links sind die gleichen physikalischen Knoten, die Sie bereits wissen, dass diese ganze Teilbäume sind identisch.

Einer C-Implementierung könnte...

bool tree_compare (const node* t1, const node* t2)
{
  //Same node check - also handles both NULL case
  if (t1 == t2)  return true;

  //Gone past leaf on one side check
  if ((t1 == NULL) || (t2 == NULL))  return false;

  //Do data checks and recursion of tree
  return ((t1->data == t2->data) && tree_compare (t1->left,  t2->left )
                                 && tree_compare (t1->right, t2->right));
}

BEARBEITEN In Reaktion auf einen Kommentar...

Die Laufzeit für einen vollständigen Baum, der Vergleich mit dieser ist die meisten einfach, angegeben als O(n) wobei n ein bisschen die Größe eines Baumes. Wenn Sie bereit sind, zu akzeptieren, eine mehr komplexe gebunden, die Sie bekommen können, eine kleinere z.B. O(minimum(n1, n2)), wobei n1 und n2 die Größen der Bäume.

Die Erklärung ist im Grunde, dass der rekursive Aufruf nur (höchstens) einmal für jeden Knoten im linken Baum, und nur (höchstens) einmal für jeden Knoten im rechten Baum. Als die Funktion selbst (ohne Rekursion) nur gibt bei den meisten eine Konstante Menge an Arbeit (es gibt keine Schleifen), das Werk, einschließlich aller rekursiven Aufrufe kann nur so viel wie die Größe des kleineren Baumes Zeiten konstant.

Könnten Sie analysieren weiter, um mehr komplexe, aber auch kleinere gebunden mit der Idee von der Kreuzung der Bäume, aber big O gibt nur eine Obere Schranke - nicht unbedingt die niedrigste Obere Schranke. Es ist wahrscheinlich nicht lohnt zu tun, die Analyse, es sei denn, Sie versuchen, zu bauen, ein größeres Algorithmus/Datenstruktur mit diesem als ein Bestandteil und als Ergebnis Sie wissen, dass eine Eigenschaft immer gilt, zu den Bäumen, die können es Ihnen ermöglichen, eine engere Schranke für die größeren Algorithmus.

Einen Weg zu bilden, ein tigher gebunden ist, zu betrachten, die Sätze von Pfaden zu Knoten in beiden Bäumen. Jeder Schritt ist entweder ein L (Linker Teilbaum) oder R (rechter Teilbaum). Also die Wurzel wird angegeben mit einem leeren Pfad. Das Rechte Kind des linken Kind der Wurzel ist "LR". Definieren Sie eine Funktion "in Pfade (T)" (mathematisch - nicht Teil des Programms) zur Vertretung der Satz von gültigen Pfaden in einem Baum - ein Weg für jeden Knoten.

So haben wir vielleicht...

paths(t1) = { "", "L", "LR", "R", "RL" }
paths(t2) = { "", "L", "LL", "R", "RR" }

Den gleichen Pfad Angaben gelten für beide Bäume. Und jeder Rekursion folgt immer dem gleichen Links - /rechts-link für beide Bäume. Damit die Rekursion Besuche die Pfade in der itersection dieser Gruppen, und die festesten gebunden, wir können angeben dies ist die Kardinalität von dieser Kreuzung (immer noch mit der ständigen gebunden auf Arbeit pro rekursiven Aufruf).

Für die Baum-Strukturen vor, wir tun rekursionen für die folgenden Pfade...

paths(t1) intersection paths(t2) = { "", "L", "R" }

Damit unsere Arbeit ist in diesem Fall begrenzt auf höchstens drei mal die maximalen Kosten für nicht-rekursive Arbeit in der tree_compare Funktion.

Dies ist normalerweise unnötig viel detail, aber klar der Kreuzung des Weges-sets ist höchstens so groß wie die Anzahl der Knoten im kleinsten ursprüngliche Baum. Und ob die n in O(n) bezeichnet die Anzahl der Knoten in einem ursprünglichen Baumes oder die Summe der Knoten in den beiden, das ist eindeutig nicht kleiner als die minimale oder unsere Kreuzung. Daher O(n) ist nicht so fest gebunden, aber es ist immer noch eine gültige Obergrenze, auch wenn wir ein bisschen vage, welche Größe wir reden.

InformationsquelleAutor der Antwort Steve314

Können wir auch einen der zwei traversalen (pre-order, post-order und in-order) und vergleichen Sie dann die Ergebnisse der beiden Bäume. Wenn Sie gleich sind, können wir sicher sein, dass Ihre Gleichwertigkeit.

InformationsquelleAutor der Antwort Pranav

Da es eine nachgewiesene Tatsache, dass es möglich ist, wieder eine binary tree, solange haben wir die folgenden:

1. Die Sequenz von Knoten, die auftreten, in einer In-Order-Traversal.
2. Die Sequenz von Knoten, die gefunden werden, in einer Pre-Order-ODER Post-Order-Traversal

Wenn zwei binäre Bäume haben die gleiche Ordnung und [pre-order und post-order] Reihenfolge, dann sollten Sie auch gleich die beiden strukturell und in Bezug auf Werte.

Jeder traversal ist eine O(n) - operation. Die traversalen sind fertig, 4 mal insgesamt, und die Ergebnisse aus der gleichen-Typ-traversal ist im Vergleich.
O(n) * 4 + 2 => O(n)
Also, die Summe, um die Zeit-Komplexität wäre O(n)

InformationsquelleAutor der Antwort hipsandy