Welche Kombinationen der Sequentialisierung vor und nach und in Ordnung sind einzigartig?

Question

Wir kennen nach der Bestellung,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

und Vorbestellung

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

und in-Ordnung durchquer. Sequentialisierung.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

Man kann leicht erkennen, dass keiner von beiden einen bestimmten Baum eindeutig beschreibt, auch wenn wir paarweise verschiedene Schlüssel/Etiketten annehmen.

Welche Kombinationen der drei können an diesem Ende verwendet werden und welche nicht?

Positive Antworten sollten einen (effizienten) Algorithmus umfassen, um den Baum zu rekonstruieren, und einen Beweis (Idee), warum er korrekt ist. Negative Antworten sollten Gegenbeispiele liefern, dh verschiedene Bäume, die die gleiche Darstellung haben.

Answer 1

Zunächst gehe ich davon aus, dass alle Elemente unterschiedlich sind. Keine Menge an Sequentialisierungen wird Ihnen die Form eines Baumes mit Elementen mitteilen [3,3,3,3,3]. Es ist natürlich möglich, einige Bäume mit doppelten Elementen zu rekonstruieren. Ich weiß nicht, was schöne Bedingungen gibt.

Wenn Sie die negativen Ergebnisse fortsetzen, können Sie einen Binärbaum nicht vollständig aus seinen vorbestellten und nach der Bestellung nur nach Bestellungen neu aufbauen. [1,2] Vorbestellung, [2,1] Nach der Bestellung muss haben 1 an der Wurzel, aber 2 Kann entweder das linke Kind oder das rechte Kind sein. Wenn Sie sich für diese Mehrdeutigkeit nicht interessieren, können Sie den Baum mit dem folgenden Algorithmus rekonstruieren:

• Sei $ [x_1, dots, x_n] $ der vorbestellige Traversal und $ [y_n, ldots, y_1] $ der nach der Bestellung. Wir müssen $ x_1 = y_1 $ haben, und dies ist die Wurzel des Baumes.
• $ x_2 $ ist das linke Kind der Wurzel, und $ y_2 $ ist das ganz rechts Kind. Wenn $ x_2 = y_2 $, ist der Stammknoten unär; Übernehmen Sie über $ [x_2, ldots, x_n] $ und $ [y_n, ldots, y_2] $, um den einzelnen Subtree zu erstellen.
• Ansonsten sei $ i $ und $ j $ die Indizes so, dass $ x_2 = y_i $ und $ y_2 = x_j $. $ [x_2, ldots, x_ {j-1}] $ ist die Vorbestellung des linken Teilbaum . Das linke Subtree hat $ J-2 = N-I+1 $ Elements und der rechte Subtree $ I-2 = N-J+1 $ Elements. Wiederholen Sie dies einmal für jeden Subtree.
  Übrigens verallgemeinert diese Methode auf Bäume mit willkürlicher Verzweigung. Finden Sie mit willkürlicher Verzweigungen das Ausmaß des linken Unterbaums heraus und schneiden Sie seine $ j-2 $ -Lemente aus beiden Listen ab, um den zweiten Subtree von links abzuschneiden, und so weiter.

Wie bereits erwähnt, beträgt die Laufzeit $ o (n^2) $ mit $ theta (n^2) $ Worst (im Fall mit zwei Kindern suchen wir jede Liste lineraly). Sie können dies in $ o (n , mathhrm {lg} (n)) $ machen, wenn Sie die Listen für die Erstellung einer $ n , mathem {lg} (n) $ Finite -Map -Struktur von Elementwerten zu Positionen vorbereiten In den Eingabelisten. Verwenden Sie auch ein Array oder eine endliche Karte, um von Indizes zu Werten zu wechseln. Halten Sie sich an globale Indizes, so dass rekursive Anrufe die gesamten Karten erhalten und ein Bereich als Argument nehmen, um zu wissen, worauf man reagieren soll.

Mit dem Vorbestellungspunkt $ [x_1, ldots, x_n] $ und der In-Ordnung-Traversal $ [Z_1, ldots, Z_N] $ können Sie den Baum wie folgt wieder aufbauen:

• Die Wurzel ist der Kopf des Vorbestellungs-Traversal $ x_1 $.
• Sei $ k $ der Index, so dass $ z_k = x_1 $. Dann $ [z_1, ldots, z_ {k-1}] $ ist der in Ordnung des linke Kind Richtiges Kind. An der Anzahl der Elemente, $ [x_2, ldots, x_k] $ ist die Vorbestellung des linken Kindes und $ [x_ {k+1}, ldots, x_n] $ das des rechten Kindes. Wiederholen Sie sie, um die linken und rechten Unterbälde zu bauen.

Auch hier ist dieser Algorithmus $ o (n^2) $ wie angegeben und kann in $ o (n , mathhrm {lg} (n)) $ durchgeführt werden, wenn die Liste in eine endliche Karte von Werten zu Positionen vorverarbeitet wird .

Post-Order plus In-Order ist natürlich symmetrisch.