Konvertieren Preorder Auflistung eines binären Baum zu Postorder und umgekehrt

Question

Wie kann ich das Preorder-Angebot eines Baumes finden, wenn nur der Postorder-Eintrag angegeben wird und umgekehrt. Auch in dem Baum, jeder Nicht-Blattknoten hat zwei Kinder (das heißt Jeder Knoten hat entweder zwei oder null Kinder.)

EDIT: Ein andere gegebene Annahme ist, dass das Etikett jeden Knotens ist einzigartig und hat ein Feld, das es als internen Knoten oder ein Blatt zu identifizieren. Ich denke, das sollte die Mehrdeutigkeit ein einzelne vorbestellen oder Postorder in der Lage, um loszuwerden, um eindeutig einen Baum zu identifizieren.

Answer 1

Ohne davon aus, dass Knoten im Baum ein Feld haben, die sich als interne oder Blatt idenrify, können Sie nicht eine eindeutige Antwort auf Ihre Frage finden. Diese Annahme oder Inorder Auflistung muss verfügbar sein, einen einzigartigen Baum zu finden. In diesem Fall ist eine mögliche Antwort zu finden, können Sie einen Baum des Formulars unten konstruieren können beliebigen Postorder-Eintrag entsprechen: (suppose Postorder-Auflistung ist: 1 2 3 4 5 6 7 8 9)

9[7[5[3[1,2],4],6],8]

Jetzt können Sie machen Preorder Auflistung diesen Baum verwendet wird.

Unter der Annahme, Knoten im Baum ein Feld hat, die sich als internes oder Blatt zu identifizieren, können wir für diese Art von Bäumen mit diesem Algorithmus einen einzigartigen Baum aus einem Postorder Angebote machen:

1. Sweep von Anfang an der Postorder-Liste und den ersten internen Knoten finden. Dieser Knoten wird genau zwei Blatt Kinder hat, die diesen Knoten in Postorder-Liste vorangestellt werden.
2. In Ihrer Baumstruktur hinzufügen, dass die internen Knoten und macht zwei vorhergehende Knoten in der Auflistung seiner Kinder.
3. Entfernen die beiden Kinder von der Auflistung und dass interne Knoten ein Blatt machen.
4. Gehen Sie zu Schritt 1 und wiederholen, bis Eintrag leer wird.

Answer 2

Betrachten sie die rekursive Struktur einer Vorordnungsdurchquerung:

T(r) = [r, T(r->left), T(r->right)]
where T(r) is the preorder traversal of tree rooted at node r

Dann wissen wir, dass die Wurzel eines Baumes durch T (r) beschrieben ist immer der erste Knoten in der Traversal.

Mit diesem Wissen, und zu wissen, dass eine Wurzel ist immer höher in einem Baum als seine Teilbäume, darüber nachzudenken, wie Sie diese Informationen verwenden würden den Baum neu zu erstellen. Denken Sie rekursiv.

Vorab: dies kann nur geschehen, wenn dies ein binärer Suchbaum ist , die Knoten, so dass left-child < root < right-child beschränkt. Im Allgemeinen Bäume können nicht von einem einzigen Traversal rekonstruiert werden. Siehe diese hervorragende Ressource für eine ausführlichere Erklärung .

Mehrdeutigkeit noch existiert unabhängig von der Regel etwa 0 oder 2 Kinder:

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

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

Beide haben die Vorordnungsdurchquerung [4 2 1 3 5 6 7]

Answer 3

Zum Beispiel: Sie sind verpflichtet, Postorder-Form zu konvertieren form.this vorbestellen kann auf folgende Art und Weise durchgeführt werden. Post bestellen: DEBFCA Preorder: ABDECF sehen wir, dass A die Wurzel ist. und aus preorder können wir feststellen, dass der Knoten B zu A.therefore gelassen schaffen wir zwei Unterklassen, die (BED) (CF), wenn wir .now B durchlaufen wir es als Wurzel nehmen, und wir sehen, dass nach B, D PRESENT IS , bedeutet dies, D nach B links und E ist direkt nach B .now wir C.take es als root.then durchqueren F vorhanden, nachdem C ist, so dass es als links genommen wird.