Traversierungsalgorithmen🔖

Wir haben schon drei Traversierungsmöglichkeiten kennengelernt. Jetzt versuchen wir für die drei rekursive Alogrithmen zu entwicklen.

Pre-Order🔖

1. Betrachte das Objektdiagramm und gib die Reihenfolge an in der die Kontakte durchlaufen werden. Schreibe dazu die Reihenfolge der Benutzernamen auf.
2. Löse das Code-Puzzle zur Pre-Order-Methode.
3. Führe den Algorithmus am Objektdiagramm aus.

Post-Order🔖

1. Betrachte das Objektdiagramm und gib die Reihenfolge an in der die Kontakte durchlaufen werden. Schreibe dazu die Reihenfolge der Benutzernamen auf.
2. Formuliere einen Algorithmus im Pseudocode in Anlehnung an das Code-Puzzle.
3. Führe den Algorithmus am Objektdiagramm aus.

In-Order🔖

1. Betrachte das Objektdiagramm und gib die Reihenfolge an in der die Kontakte durchlaufen werden. Schreibe dazu die Reihenfolge der Benutzernamen auf.
2. Formuliere einen Algorithmus im Pseudocode in Anlehnung an das Code-Puzzle.
3. 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.

1. Modifiziere den Pre-Order-Algorithus so, dass überprüft wird, ob ein Objekt im Binärbaum enthalten ist. Die Methode soll searchPreOrder heißen und true zurückgeben, wenn das Objekt pContent enthalten ist und false, wenn dies nicht der Fall ist.
2. Teste deine Modifizierung am Objektdiagramm. Teste beide Fälle. Beginne damit, dass das Objekt enthalten ist.
3. Analysiere wie viele Schritte im schlechtesten Fall nötig sind, um herauszufinden, ob ein Objekt enthalten ist.
4. Überlege wie man den Binärbaum modifizieren könnte, sodass man schneller suchen kann.