Traversierungsalgorithmen
Auf der Seite Traversierung hast du die drei Reihenfolgen von Hand durchgespielt. Jetzt schreibst du sie als rekursive Algorithmen auf.
Alle drei haben denselben Bau – sie unterscheiden sich in einer einzigen Zeile:
preOrder(baum):
wenn baum leer ist: fertig
gib den Inhalt aus <-- Wurzel zuerst
preOrder(linker Teilbaum)
preOrder(rechter Teilbaum)Für In-Order rutscht die Ausgabezeile zwischen die beiden Aufrufe, für Post-Order hinter sie. Sonst ändert sich nichts.
Der Basisfall ist immer derselbe: ein leerer Knoten. Das ist der Grund, warum man nie auf null prüfen muss – die Abiturklasse legt unter jedem gefüllten Knoten zwei leere an, und auf denen bricht die Rekursion ab.
Pre-Order
- Betrachte das Objektdiagramm und gib die Reihenfolge an, in der die Kontakte durchlaufen werden. Schreibe dazu die Reihenfolge der Benutzernamen auf.
- Löse das Code-Puzzle unten zur Pre-Order-Methode und ordne dort die Kontakte in die Reihenfolge, die du aufgeschrieben hast.
- Führe den Algorithmus am Objektdiagramm aus.
Post-Order
- Betrachte das Objektdiagramm und gib die Reihenfolge an, in der die Kontakte durchlaufen werden. Schreibe dazu die Reihenfolge der Benutzernamen auf.
- Formuliere einen Algorithmus im Pseudocode in Anlehnung an das Pre-Order-Puzzle. Mit dem Code-Puzzle unten kannst du dich anschließend kontrollieren.
- Führe den Algorithmus am Objektdiagramm aus.
In-Order
- Betrachte das Objektdiagramm und gib die Reihenfolge an, in der die Kontakte durchlaufen werden. Schreibe dazu die Reihenfolge der Benutzernamen auf.
- Formuliere einen Algorithmus im Pseudocode in Anlehnung an das Pre-Order-Puzzle. Mit dem Code-Puzzle unten kannst du dich anschließend kontrollieren.
- Führe den Algorithmus am Objektdiagramm aus.
Suchen in Binärbäumen
Im Binärbaum soll überprüft werden, ob ein bestimmtes Objekt enthalten ist.
a) Modifiziere den Pre-Order-Algorithmus so, dass er prüft, ob ein Objekt im Binärbaum enthalten ist. Die Methode soll searchPreOrder heißen und true zurückgeben, wenn pContent enthalten ist, sonst false.
b) Teste deine Fassung am Objektdiagramm, und zwar beide Fälle. Fang mit dem Fall an, dass das Objekt enthalten ist.
c) Analysiere, wie viele Schritte im schlechtesten Fall nötig sind.
d) Überlege, wie man den Binärbaum ändern könnte, damit die Suche schneller wird.
Auflösung
a) Aus dem Ausgeben wird ein Vergleichen, und die beiden rekursiven Aufrufe werden mit oder verknüpft:
searchPreOrder(baum, pContent):
wenn baum leer ist: gib false zurück
wenn Inhalt = pContent: gib true zurück
gib searchPreOrder(linker Teilbaum, pContent)
ODER searchPreOrder(rechter Teilbaum, pContent) zurückb) Ist das Objekt enthalten, meldet einer der beiden Aufrufe true, und das true wird nach oben durchgereicht. Ist es nicht enthalten, laufen alle Äste bis zu den leeren Knoten und liefern false.
c) Alle Knoten, also n Schritte. Der Pre-Order-Durchlauf weiß nicht, wo er suchen soll – er kann nur jeden Knoten anschauen. Das ist genauso viel wie bei einer linearen Liste; der Baum bringt hier also gar nichts.
d) Man müsste die Inhalte so anordnen, dass sich an jedem Knoten entscheiden lässt, in welchem der beiden Teilbäume weitergesucht werden muss – dann fiele die Hälfte bei jedem Schritt weg. Genau das ist der binäre Suchbaum.