Verknüpfen von binären Bäumen

Question

Angenommen, wir haben eine Reihe von binären Bäumen mit ihren Inorder- und Preorder-Traversalen gegeben, und wo kein Baum ein Unterbaum eines anderen Baumes in der gegebenen Menge ist. Nun wird ein weiterer Binärbaum Q gegeben. Finden Sie heraus, ob er durch Verbinden der Binärbäume aus der gegebenen Menge gebildet werden kann (während das Verbinden von jedem Baum in der Menge fast einmal in Betracht gezogen wird), bedeutet:

Wählen Sie die Wurzel von jeden Baum in der Menge und haken Sie ihn an einen beliebigen Eckpunkt eines anderen Baums an, so dass der resultierende Baum ebenfalls ein Binärbaum ist.

Können wir dies mit LCA (Least Common Ahnen) tun oder braucht es eine spezielle Datenstruktur zu lösen?

Answer 1

Ich denke, eine binäre Baumstruktur sollte ausreichen. Ich glaube nicht, dass Sie irgendeine andere spezielle Datenstruktur benötigen.

Und ich verstehe nicht, wie Sie LCA dafür verwenden würden. Soweit ich weiß, wird LCA verwendet, um den niedrigsten gemeinsamen Vorfahren für zwei NODES im selben Baum zu kennen. Es würde nicht helfen, zwei Bäume zu vergleichen. (was ich tun würde, um zu überprüfen, ob Q gebildet werden kann)

Meine Lösung in Worten.

Der Baum Q, der überprüft werden muss, ob er aus der Menge der Bäume gemacht werden kann, also würde ich einen Top-Down-Ansatz wählen. Grundsätzlich Q mit den möglichen Bäumen vergleichen, die aus der Menge gebildet werden.

Logik: wenn Q.root mit keinem der Wurzeln der Bäume in der Menge übereinstimmt (A, B, C .... Z ...), keine Lösung möglich.

Wenn Q.root mit einem Baumstamm übereinstimmt (zB A), markieren Sie die entsprechenden untergeordneten Elemente und markieren Sie A als verwendet/besucht. (Was ich von der Frage verstehe: ein Baum kann nur einmal verwendet werden)

Wir sollten mit A in unserer Lösung nur fortfahren, wenn alle Kinder von Q mit den entsprechenden Kindern von A übereinstimmen. (Ich würde Tiefenüberquerung machen , Breathth First würde auch funktionieren).

Wir können einen neuen Baum aus der Menge hinzufügen (d. H. Eine neue Wurzel (Baum B) nur an Blattknoten von A anhängen, da wir den Binärbaum pflegen müssen). Verfolgen Sie, wo das B angehängt wurde.

Wiederholen Sie die gleiche Überprüfung mit dem entsprechenden Kindervergleich wie für A. Wenn keine Übereinstimmung gefunden wird, entfernen Sie B und versuchen Sie, C-Baum an der Stelle hinzuzufügen, an der B hinzugefügt wurde.

Wir machen dies weiter, bis wir keine Knoten mehr in Q haben. (Es sei denn, wir wollen IDENTICAL MATCH, in diesem Fall würden wir andere Baumkombinationen ausprobieren als die, die Q haben, aber mehr Knoten haben) .

Entschuldigung für die ausführliche ausführliche Antwort. (Ich denke, dass mein Pseudocode schwer zu schreiben und mit Kommentaren zu erklären wäre).

Hoffe, das hilft.

Eine alternative Lösung: Wird viel weniger effizient sein (versuchen Sie nur, wenn es relativ wenig Bäume gibt): alle möglichen Bäume bilden (zuerst in 2s dann 3s .... N) und und Überprüfen der gebildeten Bäume wenn sie identisch sind der Vergleichsteil auf Q. kann hier genannt werden: http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/