Bäume Iterative Lösungen

Tim Rieber
Erstie
Erstie
Beiträge: 16
Registriert: 18. Apr 2017 17:42

Bäume Iterative Lösungen

Beitrag von Tim Rieber » 19. Sep 2017 15:07

Ich habe Probleme mit Aufgaben, bei denen auf alle Elemente einer Baumstruktur iterativ eine Operation angewendet werden soll.

Zum Beispiel: Manipulation einer Struktur: invert (iterativ). Ich finde keinen Ansatz, wie ich iterativ die invert-Operation auf alle Knoten ausführen kann. Die invert-Operation auf eine key-Menge von einem Knoten anzuwenden ist kein Problem, aber ich bleibe hängen, wenn ich formulieren soll, wie ich ohne Rekursion jeden Knoten ansprechen kann.

Würde mich sehr über einen kleinen Tipp/Ansatz freuen!

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: Bäume Iterative Lösungen

Beitrag von Hans123 » 19. Sep 2017 16:27

Du kannst den Baum via Stack durchgehen. Das ist aber womöglich in der Klausur nicht erlaubt, da der Stack in java.util ist, wurde uns aber so in der VL beigebracht. Dann kannst du mit einem Stack S via S.push(Knoten) Knoten auf dem Stack ablegen und via S.pop() dir das oberste zurückgeben lassen und es aus dem Stack entfernen. Das packt man dann in ein while(! S.empty()).

Es gibt auch Lösungen ohne Stack, da kann ich empfehlen, mal auf youtube oder google nach 'Morris inorder traversal' zu schauen. Ist eigentlich auch nicht allzu kompliziert, wenn man es mal verstanden hat.

Tim Rieber
Erstie
Erstie
Beiträge: 16
Registriert: 18. Apr 2017 17:42

Re: Bäume Iterative Lösungen

Beitrag von Tim Rieber » 20. Sep 2017 11:56

Danke, das hat schon sehr geholfen!

Antworten

Zurück zu „Archiv“