Zum Inhalt springen

Wie rekonstruiere ich einen Baum mit Pre- und Inorder?


Empfohlene Beiträge

Hallo,

ich habe eine Aufgabe mit den Werten von Pre-Order und In-Order bekommen und weiß nicht, wie ich den Baum rekonstruieren kann. Ich weiß, dass der erste Wert von Pre-Order der Wurzel ganz oben sein soll, also die 5. Dadurch das ich den Wurzel habe, kann ich dann auch die Einteilung bei In-Order machen, also alles was links von der 5 ist, gehört zum linken Teilbaum und alles, was rechts von der 5 ist, gehört zum rechten Teilbaum. Wie gehe ich aber dann weiter vor?

Aufgabe: Rekonstruiere diesen Baum:

Pre-Order (W–L–R): 5 1 4 3 11 2 3 8 10 6 9

In-Order (L-W-R): 3 4 11 1 2 5 8 6 10 3 9

Mein bisheriger Ansatz:

Hauptwurzel (ganz oben): 5

Linker Teilbaum: 3 4 11 1 2

Rechter Teilbaum: 8 6 10 3 9

Das ist keine Hausaufgabe. Ich will das nur erklärt bekommen, damit ich es in der Klausur lösen kann. Würde mich über Hilfe freuen.

Link zu diesem Kommentar
Auf anderen Seiten teilen

  • 3 Monate später...

Ist zwar schon etwas älter, aber anbei noch die Hilfestellung: Binärbaum

Die 3 Traversierung (pre-, in- und post-Order) sind im Grunde von der Art des Durchlaufens durch den Baum gleich. Das was sie unterscheidet ist, wann das "print" / die Ausgabe des Inhaltes des Kontens aufgerufen wird.

Bei Pre-Order geben wir direkt, wenn man in einen Knoten hineingeht das Element als erstes aus und dann durchläuft man die unterhalb hängenden Teilbäume. Bei in-Order gehe ich in einen Knoten hinein, durchlaufe den linken Teilbaum, gebe das Element aus und dann durchlaufe ich den rechten Teilbaum.

Mein Tipp: Einmal den Baum aufmalen und dann würdest Du bei Pre-Order direkt die erste Zahl in das oberste Element schreiben und danach gehst Du in das linke Element unter der Wurzel und arbeitest Dich rekursiv durch. Bei der In-Order gehest Du zuerst an das tiefste linkeste Blatt und trägst dort die Zahl ein und dann steigst Du ein Element auf trägst dort die Zahl ein und gehst in den rechten Teilbaum komplett hinunter und arbeitest dann rekursiv durch.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Dein Kommentar

Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...