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

Wie bereits von anderen erwähnt, kann ein Binärbaum nicht nur durch Traversal vor und nach der Reihenfolge rekonstruiert werden. Ein einzelner Kindknoten hat mehrdeutige Traversale, die nicht erkennen lassen, ob es sich um ein linkes oder rechtes Kind handelt, z. B. die folgenden Traversale vor und nach der Reihenfolge: preorder: a,b Nachordnung b,a

Sie kann beide der folgenden Bäume erzeugen

a a \ / b b Es ist einfach nicht möglich zu wissen, ob b das linke oder rechte Kind von a ist, ohne zusätzliche Informationen wie z. B. eine Inorder-Traversal.

Answer 2

Es ist nicht möglich, einen allgemeinen Binärbaum aus Preorder- und Postorder-Traversalen zu konstruieren (siehe hier). Aber wenn wir wissen, dass der Binärbaum vollständig ist, können wir den Baum ohne Mehrdeutigkeit konstruieren. Lassen Sie uns dies anhand des folgenden Beispiels verstehen.

Betrachten wir die beiden gegebenen Arrays als pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7} und post[] = {8, 9, 4, 5, 2, 6, 7, 3, 1}; In pre[] ist das ganz linke Element die Wurzel des Baums. Da der Baum voll ist und die Arraygröße mehr als 1 beträgt, muss der Wert neben 1 in pre[] das linke Kind von Root sein. Wir wissen also, dass 1 die Wurzel und 2 das linke Kind ist. Wie findet man alle Knoten im linken Teilbaum? Wir wissen, dass 2 die Wurzel aller Knoten im linken Teilbaum ist. Alle Knoten vor 2 in post[] müssen sich im linken Teilbaum befinden. Jetzt wissen wir, dass 1 die Wurzel ist, die Elemente {8, 9, 4, 5, 2} befinden sich im linken Teilbaum, und die Elemente {6, 7, 3} befinden sich im rechten Teilbaum.

              1
            /   \
           /      \
 {8, 9, 4, 5, 2}     {6, 7, 3}

Wir folgen dem obigen Ansatz rekursiv und erhalten den folgenden Baum.

      1
    /   \
  2       3
/  \     /  \

4 5 6 7 / \
8 9