Nodes/Knoten eines Binärbaums unter einem bestimmten Node iterativ ausgeben?

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