Prof. Dr. R. Laue                                                                                                                                  SS00
                                Informatik II
                                Übungsblatt 5
                                            Abgabe: 8.6.00 bis 10.00 Uhr in der Vorlesung
URL:         /axel/informatik2_ss00_blatt5.html

Die Programmieraufgaben sind alleine zu bearbeiten, die anderen Aufgaben können in Zweiergruppen bearbeitet werden.
 

Aufgabe 9 (10 Punkte Programmieraufgabe)
Erweitern Sie nachfolgendes Programm um folgende Punkte:
1. print_baum soll einen lwr Durchlauf vornehmen.
2. insert_baum soll einen Suchbaum anlegen ohne Balancier Operationen.
3. Am Ende von main soll der Baum mit einer noch zu schreibenden Routine free_baum_matrikelnummer(struct knoten *wurzel)  gelöscht werden.
4. Füllen Sie im main Programm den Baum mit 1000 zufälligen Zahlen bevor Sie die print Routine aufrufen.
 


 

Aufgabe 10  (6 + 3 Punkte)
a) Formulieren Sie in Pseudocode einen Algorithmus zum rwl Durchlauf eines binären Baums. Der Algorithmus soll nicht rekursiv sein, sondern Sie verwalten den Durchlauf selber indem Sie einen Keller verwenden. Für den Keller haben sie an Funktionen zur Verfügung:

init = Initialisieren
push = auf den Keller legen
pop = vom Keller holen   (liefert den zuletzt eingefügten Wert oder den Wert NULL wenn der Keller leer ist)

Für den Baum verwenden Sie bitte die Datenstruktur aus der obigen Programmieraufgabe.

b) Gesetzt den Fall der binäre Baum hat 1000 Einträge. Wieviel Platz muß im Keller sein, damit Ihr Algorithmus funktioniert? Geben Sie eine untere Schranke (best case) und eine obere Schranke (wort case) an. Diese Schranken sollen in den jeweilligen Fällen auch erreicht werden! Begründung!