2010-02-02 20 views
5

Wie kann ich einen Baum aufgrund seiner Inorder- und Preorder-Traversierung konstruieren? Ich bin nur auf der Suche nach einem effizienten Algorithmus.Einen Baum konstruieren

+6

Nun, rekursiv. Ich hoffe, du bist nicht mein Schüler. –

+2

Würde etwas Klärung benötigen. Wie ist das Format der Eingabedaten? Ist der Baum ausgeglichen? Was meinst du mit effizient (Ordo (x) oder einfach "nicht schrecklich verrückt"). Welche Struktur möchten Sie erstellen? Baum als verknüpfte Objekte oder Baum mit einem Array. – ron

+1

http://forums.devshed.com/software-design-43/finding-binary-tree-from-inorder-and-preorder-traversals-151147.html – Heinzi

Antwort

4

ein eklatantes Kopieren und Einfügen von Sun's (Oracle now, I guess...) forum:

Frage:
Kann jemand mir helfen, wie Binary Baum zu konstruieren aus Inorder und Postorder-Traversierung, ich möchte nur den Algorithmus wissen, so dass ich es anwenden kann.

Antwort:
Lassen p_1, p_2...p_n die Nachordnungsdurchquerung und lassen i_1, i_2...i_n die Inorder Traversal sein. Wir wissen, dass die Wurzel des Baumes p_n ist. Finden Sie dieses Element im Inorder-Traversal, sagen wir i_1, i_2...i_k-1p_ni_k+1...i_n. Von der Invers-Traversierung finden wir alle Elemente in dem linken Teilbaum, d.h. i_1, i_2...i_k-1 und in dem rechten Teilbaum, d.h. i_k+1...i_n.

Element entfernen p_n (und Element i_k==p_n). Finden Sie das äußerste rechte Element p_j in p_1, p_2...p_j...p_n-1 wo p_j ist ein Element in i_1, i_2 ... i_k-1. Dies ist die Wurzel des linken Teilbaums des ursprünglichen Baums. Split p_1, p_2...p_j und p_j+1 ... p_n-1 und i_1, i_2...i_k-1 und i_k+1...i_n. Jetzt haben Sie zwei Untersequenzen, die die Postorder- und Inorder-Traversierung der zwei Teilbäume des ursprünglichen -Baums darstellen.

Autor: JosAH.

Ich habe den Algorithmus einmal nach Jos Anweisungen implementiert, und es hat perfekt funktioniert!

+0

Es ist zu zeitaufwendig, rechteste Element p_j in p_1 ~ p_n-1 zu finden, während es auch in i_1 ~ i_k-1 ist. Es dauert O (n^2) Zeit. Eigentlich nach dem Entfernen p_n, und finden Sie ihre Position in i_1 ~ i_n. Wir kennen die Position von p_j bereits. Dies liegt daran, dass wir bereits die Anzahl der Knoten in seinem linken und rechten Teilbaum kennen, die durch Zählen der Elemente nach p_n in i_1 ~ i_n erhalten werden können. Dadurch könnten wir leicht den Platz finden, um p_1 ~ p_n-1 zu teilen – ibread

1

Da dies Hausaufgaben sind, werde ich Ihnen keine vollständige Antwort geben, aber hoffentlich genug, um Sie in Bewegung zu bringen.

Stellen Sie sich vor, Sie haben vorbestellen Traversal von, sagen this Baum.

Die Traversal gibt Ihnen 2-7-2-6-5-11-5 ... usw. Beachten Sie, dass die 5 ist eigentlich das richtige Kind der Wurzel.

Offensichtlich können Sie das nicht aus dem Blick auf die Zahlen nur sagen, so entweder Sie werden über die Struktur des Baumes erzählt, oder Sie müssen einige zusätzliche Daten speichern (dh ob ein Knoten der Linke ist) zum Beispiel Kind oder rechtes Kind).

Das Analysieren der Struktur ist einfach eine rekursive Funktion, die die Vororder-Traversierung als Eingabe verwendet (denken Sie an Ihren Bereich, wenn Sie die Eingabe übergeben). Wie bereits erwähnt, sollte Ihr Preorder-Traversal einige zusätzliche Daten enthalten.


Effizienz:

überlegen, wie oft jeder Knoten besucht wird, wenn Sie diesen Baum bauen, sondern berücksichtigen auch den Betrieb der Eingabe zu lesen. Gibt es eine Möglichkeit, die Eingabe schneller zu reorganisieren, als Sie die Struktur erstellen können? Welche Struktur müssten Sie verwenden, wenn Sie die Daten manipulieren müssen?


In Reihenfolge: Sie brauchen die gleiche Idee, um Sie durch sie zu bekommen, so werde ich es nicht abdecken. Ich bin sicher, jemand anderes wird es tun, wenn Sie verzweifelt danach suchen.