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

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:adt:baeume:breitensuche:start [14.02.2022 19:20] – [Suche im Baum] sbelfaecher:informatik:oberstufe:adt:baeume:breitensuche:start [18.01.2024 07:31] (aktuell) – [Suche im Baum] Marco Kuemmel
Zeile 1: Zeile 1:
 ====== Levelorder Traversierung, Iterative Tiefensuche ====== ====== 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 den drei rekursiv implementierbaren Traversierungen wird der Baum zuerst in die Tiefe durchwandert bis hin zu seinen Blättern ("Tiefensuche"). Manchmal möchte man aber einen Baum auf jedem Level von links nach rechts (oder andersherum) durchlaufen, also Level für Level. Das nennt man "Level-Order-Traversierung":
  
-{{ :faecher:informatik:oberstufe:adt:baeume:traversierungen:hinweise_traversierung:preorder.gif |}}+{{ :faecher:informatik:oberstufe:adt:baeume:breitensuche:levelorder.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. 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.
 +
 +In diesem Wiki-Abschnitt wollen wird zunächst die Rekursiven Traversierungen iterativ umschreiben, um uns anschließend zu überlegen, wie man die Level-Order-Traversierung (oder **Breitensuche**) implementiert.
  
 ===== Iterative Traversierung ===== ===== Iterative Traversierung =====
Zeile 47: Zeile 49:
  
 <WRAP center round tip 95%> <WRAP center round tip 95%>
-Du kannst in der Klasse "Testbaeume" anpassen, welche baumdefinitionen geladen werden sollen: Entweder 100 "große" Bäume oder 5 "kleine" Bäume.+Du kannst in der Klasse "Testbaeume" anpassen, welche Baumdefinitionen geladen werden sollen: Entweder 100 "große" Bäume oder 5 "kleine" Bäume.
 </WRAP> </WRAP>
  
  
-  * Implementiere zunächst den Stack, so dass du anschkließen die Knoten des Baums verwalten kannst. Schlage wenn nötig auf den [[faecher:informatik:oberstufe:adt:stack:linkedstack:start|entsprechenden Wiki-Seiten]] nach. +  * Implementiere zunächst den Stack, so dass du anschließend die Knoten des Baums verwalten kannst. Schlage, wenn nötig, auf den [[faecher:informatik:oberstufe:adt:stack:linkedstack:start|entsprechenden Wiki-Seiten]] nach. 
-  * Implementiere dann die eine Iterative-Traversierung des Baums. Gelingt es dir, Pre-, In- und Postorder Traversierung zu implementieren? Mit den "kleinen" Bäumen kannst du die Traversierungen gut nachvollziehen.+  * Implementiere dann eine iterative Traversierung des Baums. Gelingt es dir, Pre-, In- und Postorder Traversierung zu implementieren? Mit den "kleinen" Bäumen kannst du die Traversierungen gut nachvollziehen.
   * Erweitere deine Traversierung zu einer Tiefensuche, die    * Erweitere deine Traversierung zu einer Tiefensuche, die 
     * einen Knoten eines bestimmten Wertes findet     * einen Knoten eines bestimmten Wertes findet
Zeile 60: Zeile 62:
 {{:aufgabe.png?nolink  |}} {{:aufgabe.png?nolink  |}}
 === (A2) Breitensuche  === === (A2) Breitensuche  ===
- * Implementiere zunächst den nötigen Queue, so dass du anschließend die Knoten des Baums verwalten kannst. Schlage wenn nötig auf den [[faecher:informatik:oberstufe:adt:stack:queue:start|entsprechenden Wiki-Seiten]] nach. + 
-  * Implementiere dann die eine Iterative-Traversierung des Baums. Gelingt es dir, Pre-, In- und Postorder Traversierung zu implementieren? Mit den "kleinen" Bäumen kannst du die Traversierungen gut nachvollziehen. +  * Implementiere zunächst die nötige Queue, so dass du anschließend die Knoten des Baums verwalten kannst. Schlage, wenn nötig, auf den [[faecher:informatik:oberstufe:adt:queue:start|entsprechenden Wiki-Seiten]] nach. Du kannst auch den vorhandenen Code für den Stack nutzen.  
-  * Erweitere deine Traversierung zu einer Tiefensuche, die +  * Implementiere dann die Level-Order-Traversierung des Baums. Gelingt es dir, die Traversierung von links nach rechts und andersherum zu implementieren? Mit den "kleinen" Bäumen kannst du die Traversierungen gut nachvollziehen. 
 +  * Erweitere deine Traversierung zu einer Breitensuche, die 
     * einen Knoten eines bestimmten Wertes findet     * einen Knoten eines bestimmten Wertes findet
     * den ersten Knoten findet, dessen Wert zwischen den an die Suchmethode zu übergebenden Parametern ''low'' und ''high'' liegt.     * den ersten Knoten findet, dessen Wert zwischen den an die Suchmethode zu übergebenden Parametern ''low'' und ''high'' liegt.
  • faecher/informatik/oberstufe/adt/baeume/breitensuche/start.1644866447.txt.gz
  • Zuletzt geändert: 14.02.2022 19:20
  • von sbel