Aufgaben

Aufgabe 3:

a)   Formuliere den Suchalgorithmus für das Suchen in einem binären Suchbaum. Der Suchalgorithmus soll zwei Werte liefern; den Wert „WAHR“ für die erfolgreiche Suche und den Wert „FALSCH“ für den Fall, dass der Begriff nicht im Baum enthalten ist.

b)   Wieviele Wörter musst du maximal lesen, bis du den gesuchten Begriff gefunden hast oder sicher weisst, dass der Begriff nicht im Baum ist?

Aufgabe 4:

a)   Erstelle einen Suchbaum mit den Namen der Schülerinnen und Schüler in deiner Klasse nach dem obigen Vorbild.

b)   Wieviele Ebenen hat er?

c)    Sind alle Ebenen vollständig besetzt?

Aufgabe 5:

Stelle dir vor, du wolltest alle Schülerinnen und Schüler deiner Schule in einem sol­chen Baum unterbringen. Wieviele Ebenen muss dieser Baum mindestens haben?

Aufgabe 6:

Erweitere den obigen Baum im Bild um die folgenden Begriffe in der angegebenen Reihenfolge durch Anhängen an den passenden Blättern:

Lot, Dom, Fee, Nut, Yps, Uhr, Art, Vieh.

Aufgabe 7:

Überlege dir, in welcher Reihenfolge du alle Elemente aus Aufgabe 6 in einem Such­­baum  anordnen kannst, so dass die „Entartungen“ beseitigt sind.

Aufgabe 8:
Stelle das Inhaltsverzeichnis eines Buches als Baum dar. Beachte, dass das kein binärer Baum sein kann, sondern jede Verzweigung eine unterschiedliche Anzahl von „Ästen“ hat. Das so dargestellte Inhaltsverzeichnis ist ein Beispiel für einen nicht binären Baum.