faecher:informatik:oberstufe:adt:baeume:breitensuche:start

Dies ist eine alte Version des Dokuments!


Levelorder Traversierung, Iterative Tiefensuche

Bei den drei rekursiv implementierbaren Traversierungen wird der Baum zuerst in die Tiefe durchwandert bis hin zu seinen Blättern ("Tiefensuche") - hier noch einmal am Beispiel bei der Preorder-Traversierung:

Bei der Levelorder Traversierung werden auf jedem Niveau des Baums erst alle Knoten besucht, bevor auf das nächste Niveau gewechselt wird, in unserem Beispielbaum ergibt sich damit die Traversierungsreihenfolge: A→B→F→C→D→G→E. Der Algorithmus zur Levelorder Traversierung ist nicht rekursiv.

Die rekursiven Implementationen der Traversierungen versagen ihren Dienst, wenn die Bäume zu tief werden, da der Call-Stack für die Rekursion nicht beliebig wachsen kann. Bei Java ist seine Größe auf ca. 256kB beschränkt, wenn diese Größe überschritten wird, erhältst du einen Stack Overflow Error:

Die einfachste Lösung für dieses Problem ist es, den Stack, in dem man darüber Buch führt, welche Knoten des Baums als nächstes zu bearbeiten sind, selbst zu verwalten.

Rekursiv Iterativ
anzahl(b: Binaerbaum): 
  falls b == null: 
    return 0 
  sonst: 
    t1 = anzahl(b.links) 
    t2 = anzahl(b.rechts)
    return 1 + t1 + t2
anzahl(b: Binaerbaum):
  todo = new Stack
  todo.push(b)
  zaehler = 0
  solange todo nicht leer:
    tmp = todo.pop()
    zaehler++ 
    falls tmp.rechts != null:
      todo.push(tmp.rechts)
    falls tmp.links != null:
      todo.push(tmp.links)
  return zaehler
FilenameFilesizeLast modified
baeume_traversierung_iterativ.odp106.8 KiB14.02.2022 14:21
baeume_traversierung_iterativ.pdf170.4 KiB14.02.2022 14:21
levelorder.gif44.1 KiB14.02.2022 19:37
stackoverflow.png13.9 KiB14.02.2022 14:24
  • faecher/informatik/oberstufe/adt/baeume/breitensuche/start.1644855331.txt.gz
  • Zuletzt geändert: 14.02.2022 16:15
  • von sbel