Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:adt:baeume:breitensuche:start [14.02.2022 17:21] – [Von der Rekursion zur Iteration] sbel
+++ faecher:informatik:oberstufe:adt:baeume:breitensuche:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== 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:
-{{ :faecher:informatik:oberstufe:adt:baeume:traversierungen:hinweise_traversierung:preorder.gif |}}
-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.
-===== Iterative Traversierung =====
-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//:
-{{ :faecher:informatik:oberstufe:adt:baeume:breitensuche:stackoverflow.png |}}
-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:
-==== Von der Rekursion zur Iteration ====
-Die folgende Tabelle stellt den rekursiven Pseudocode zur Ermittlung der Knotenzahl einer iterativen Variante gegenüber.
-^Rekursiv ^ Iterativ ^
-|<code>anzahl(b: Binaerbaum):
-  falls b == null:
-    return 0
-  sonst:
-    t1 = anzahl(b.links)
-    t2 = anzahl(b.rechts)
-    return 1 + t1 + t2</code>|<code>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</code>|
-Während die rekursive Variante die Verwaltung der noch zu bearbeitenden Knoten dem Aufrufstack der Rekursion überlässt, implementiert die iterative Variante einen eigenen "todo"-Stack mit, dem die den in den nächsten Schritten zu verarbeitenden Knoten verwaltet werden.
-===== Suche im Baum =====
-===== Material =====
-{{simplefilelist>.:*}}