Rekonstruktion eines Baums aus seinen Listen der Vor- und Nachordnung

Question

Stellen Sie sich die Situation vor, dass Sie zwei Listen von Knoten haben, von denen Sie nur wissen, dass die eine eine Darstellung eines Traversals vor der Ordnung eines Baumes und die andere eine Darstellung eines Traversals nach der Ordnung desselben Baumes ist.

Ich glaube, dass es möglich ist, den Baum genau aus diesen beiden Listen zu rekonstruieren, und ich glaube, ich habe einen Algorithmus dafür, aber ich habe ihn nicht bewiesen. Da dies ein Teil einer Masterarbeit sein wird, muss ich absolut sicher sein, dass es möglich und korrekt ist (mathematisch bewiesen). Da dies jedoch nicht der Schwerpunkt der Arbeit sein wird, habe ich mich gefragt, ob es eine Quelle gibt (z. B. eine Arbeit oder ein Buch), die ich für den Beweis zitieren könnte. (Vielleicht in TAOCP? Kennt jemand den Abschnitt?)

Kurz gesagt, ich brauche einen bewährten Algorithmus in einer zitierfähigen Ressource, der einen Baum aus seinen Traversalen vor und nach der Reihenfolge rekonstruiert.

---

Anmerkung: Der fragliche Baum wird wahrscheinlich nicht binär oder ausgeglichen sein oder irgendetwas, das ihn zu einfach machen würde.

Anmerkung2: Noch besser wäre es, nur die Liste der Vorbestellungen oder der Nachbestellungen zu verwenden, aber ich glaube nicht, dass dies möglich ist.

Anmerkung3: Ein Knoten kann eine beliebige Anzahl von Kindern haben.

Hinweis4: Ich interessiere mich nur für die Reihenfolge der Geschwister. Links oder rechts spielt keine Rolle, wenn es nur ein Kind gibt.

Answer 1

Vorordnung und Nachordnung definieren einen Baum nicht eindeutig.

Im Allgemeinen definiert ein einziger Baumdurchlauf nicht eindeutig die Struktur des Baums. Wie wir gesehen haben, ist zum Beispiel für beide für die beiden folgenden Bäume ein Traversal in der Reihenfolge [1,2,3,4,5,6] ergibt.

    4                     3
   / \                   / \
  2   5                 2   5
 / \   \               /   / \
1   3   6             1   4   6

Die gleiche Mehrdeutigkeit besteht bei Vor- und Nachreihenfolge Traversalen. Der Preorder-Traversal für den ersten Baum oben lautet [4,2,1,3,5,6]. Hier ist ein anderer Baum mit der gleichen Vorordnung Traversal.

    4
   / \
  2   1
     / \
    3   6
     \
      5

Auf ähnliche Weise können wir leicht einen anderen Baum konstruieren, dessen Postorder Traversal [1,3,2,6,5,4] mit dem des ersten Baums übereinstimmt.

Answer 2

Sie können nicht nur eine Liste verwenden, weil Sie dann kein Gefühl für die Tiefe des Baums bekommen. Sie benötigen also auf jeden Fall zwei oder mehr Listen.

Hier ist mein Versuch einer Lösung:

Verwenden Sie Ihr Pre-Order-Traversal als Mittel, um die Reihenfolge der Daten zu kennen. Dies ist sinnvoll, da Sie wissen, dass der erste Knoten der oberste ist, und Sie wissen, dass Daten, die sich weiter links im Traversal befinden, zur linken Seite des Baums gehören usw.

Ihr Post-Order-Traversal kann die Tiefe des Baums bestimmen. Nehmen wir zum Beispiel an, ich habe eine Struktur wie diese:

      1
  2   5   6
 3 4  7

Where 2 is the parent of 3 and 4, and 5 is the parent of 7.

Preorder: 1 2 3 4 5 7 6
Postorder: 3 4 2 7 5 6 1

Wir wissen, dass wir mit 1 beginnen, da dies der erste Knoten im Preorder-Traversal ist. Dann sehen wir uns die nächste Zahl an, 2. Da die Zahl 2 in der Post-Order VOR dem Knoten 1 steht, wissen wir, dass 2 ein Kind von 1 sein muss. Als nächstes sehen wir uns 3 an. 3 steht vor 2, und somit ist 3 ein Kind von 2. 4 steht vor 2, aber nach 3, also wissen wir, dass 4 ein Kind von 2 ist, aber NICHT ein Kind von 3. Etc.

Das funktioniert vielleicht nicht, wenn die Knoten nicht eindeutig sind, aber es ist zumindest ein Anfang für eine Lösung.

Editar: Die Reihenfolge der Kinder bleibt bei dieser Lösung erhalten, da die Reihenfolge der Knoten über das Preorder-Traversal und die Struktur über das Postorder-Traversal bekannt ist.

Bearbeiten2: Der Beweis könnte hier liegen: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel2%2F215%2F626%2F00017225.pdf%3Farnumber%3D17225&authDecision=-203

Ich glaube, Sie müssen das Dokument jedoch kaufen...

Hier ist ein schriftlicher Beweis, der als Lösung präsentiert wird:

http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf

Answer 3

Betrachten Sie einen beliebigen Baum T als das Vierfache (A, B, C , D ), wobei A der Wurzelknoten und B der Wurzelknoten des ersten Kindes ist, C ist ein Vektor beliebiger nicht leerer Kinder von B und D ist ein Vektor beliebiger nicht leerer Geschwister von B. Die Elemente von C y D sind selbst Bäume.

Einer von A, B, C y D leer sein kann. Wenn B leer ist, muss es auch C y D Wenn A, dann alles.

Da die Knoten eindeutig sind, sind die Mengen der Knoten, die irgendwo innerhalb der C y D sind disjunkt, und keines von beiden enthält A oder B.

Funktionen vor() y post() geordnete Sequenzen der Form erzeugen:

vor(T) \= [A, B, vor( C ) , vor( D ) ]

post(T) \= [ post( C ) , B, post( D ) , A]

wobei die auf einen Vektor angewandte Funktion definiert ist als die Verkettung der Sequenzen, die sich aus der Anwendung der Funktion auf jedes einzelne Element ergibt.

Betrachten Sie nun die Fälle:

• wenn A leer ist, ist die Ausgabe beider Funktionen die leere Folge []
• wenn B leer ist, ist die Ausgabe beider Funktionen nur [A]
• wenn C y D leer sind, vor(T) \= [A, B] und post(T) \= [B, A]
• wenn nur C leer ist, vor(T) \= [A, B, D' ] und post(T) \= [B, D'' , A] (wobei die Primzahlen eine Permutation der Knoten innerhalb von D )
• wenn nur D leer ist, vor(T) \= [A, B, C' ] und post(T) \= [ C'' , B, A]
• wenn keine leer sind, vor(T) \= [A, B, C' , D' ] und post(T) \= [ C'' , B, D'' , A]

In allen Fällen können wir die Mitglieder der beiden Ausgabesequenzen eindeutig in die entsprechenden Teilsequenzen aufteilen, indem wir A und B (falls vorhanden) als Begrenzer verwenden.

Die Frage ist also, ob wir auch die Vektorsequenzen partitionieren können. Wenn wir das können, dann kann jede rekursiv verarbeitet werden und wir sind fertig.

Da das Ergebnis von vor() wird immer eine Kette von Sequenzen sein ab mit A-Knoten, und das Ergebnis von post() wird immer eine Kette von Sequenzen sein Ende mit A-Knoten, können wir sie tatsächlich aufteilen, bereitgestellt dass die A-Knoten nie leer sind.

Dies ist der Punkt, an dem der Prozess im Falle von binären (oder auch beliebigen) Bäumen mit festen Kindern, die unabhängig voneinander leer sein können, scheitert. In unserem Fall haben wir jedoch definiert C y D nur nicht leere Knoten enthalten, so dass die Rekonstruktion garantiert funktioniert.

Ähm, ich glaube schon. Natürlich ist dies nur ein Argument, kein formaler Beweis!

Answer 4

Erstellen Sie einen binären Baum mit dieser Einschränkung, der mindestens einen Knoten hat, der nur ein Kind hat (rechts oder links, es gibt keinen Unterschied).

Schreiben Sie nun seine Preorder- und Postorder-Listen auf. Versuchen Sie dann, den Baum aus diesen Listen zu rekonstruieren. und Sie stellen fest, dass Sie bei diesem Knoten nicht entscheiden können, ob sein Kind rechts oder links ist.

Answer 5

Die Traversalen vor und nach der Reihenfolge reichen aus, um den Baum zu rekonstruieren, vorausgesetzt, die Knoten sind eindeutig benannt. Der Schlüssel zur Erstellung der entsprechenden Algorithmen liegt darin, zu verstehen, dass

X ist ein Vorfahre von Y, wenn X in der Vorordnung vor Y und in der Nachordnung nach Y steht.

Auf diese Weise können wir immer alle Nachkommen eines beliebigen Knotens finden. Die Nachkommen von X folgen immer unmittelbar auf X in der Vorordnung und gehen X in der Nachordnung voraus. Sobald wir also wissen, dass wir daran interessiert sind, den Teilbaum mit der Wurzel X zu erzeugen, können wir die Traversierung der Vor- und Nachordnung für den Teilbaum mit der Wurzel X extrahieren. Dies führt natürlich zu einem rekursiven Algorithmus, sobald wir erkennen, dass der Knoten unmittelbar nach X sein ganz linkes Kind sein muss, wenn er überhaupt ein Nachkomme ist.

Es gibt auch eine stapelbasierte Implementierung, die durch die Vorordnungsknoten iteriert und alle Knoten auf dem Stapel behält, die als direkte Eltern des nächsten Vorordnungsknotens in Frage kommen. Für jeden Vorordnungsknoten werden wiederholt alle Knoten vom Stapel genommen, die nicht Eltern des nächsten Vorordnungsknotens sind. Machen Sie diesen Knoten zu einem Kind des obersten Knotens auf dem Stapel, und schieben Sie das Kind auf den Stapel.