Nodes/Knoten eines Binärbaums unter einem bestimmten Node iterativ ausgeben?
Moin, bin aktuell bei Bäumen in Informatik angekommen und wollte fragen ob es einen Weg gibt alle Values von den Knoten unterhalb eines bestimmten Elements auszugeben, hab bereits auf StackOverflow gesucht aber nichts gefunden. Code bzw genauer Lösungsvorschlag wäre hilfreich. Programmiersprache ist Java ^^
1 Antwort
Da zu jedem rekursiven Verfahren ein semantisch äquivalentes iteratives existiert, geht das natürlich (in der Theorie).
Für ein iteratives Abklappern des Baumes bräuchte man ein paar Variablen, zumindest
- aktueller Knoten
- voriger Knoten
(können auch null sein)
Start:
voriger Knoten <-- null
aktueller Knoten <-- Wurzelknoten des Baums
Abbruch:
aktueller Knoten ist null
Iteration:
wenn voriger Knoten null oder Elternknoten des aktuellen ist
dann
wenn aktueller Knoten Kindknoten hat
dann
nächster Knoten <-- erster Kindknoten des aktuellen
sonst
nächster Knoten <-- Elternknoten des aktuellen (kann auch null sein)
sonst (voriger Knoten muss ein Kindknoten des aktuellen sein)
wenn aktueller Knoten weitere Kindknoten hat (bei Binärbaum natürlich maximal einen weiteren)
dann
nächster Knoten <-- nächster Kindknoten des aktuellen
sonst
nächster Knoten <-- Elternknoten des aktuellen (kann auch null sein)
(Verschiebung:)
voriger Knoten <-- aktueller Knoten
aktueller Knoten <-- nächster Knoten
Verarbeitung:
wenn voriger Knoten null oder Elternknoten des aktuellen ist
dann
aktuellen Knoten bearbeiten (z. B. Inhalt ausgeben)
Lässt sich natürlich noch erheblich vereinfachen