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.
 

#include <stdio.h>
struct knoten {
        struct knoten *links;
        struct knoten *rechts;
        int wert;
        };

struct knoten *new_knoten(int wert)
        {
        struct knoten *hilf;
        hilf = (struct knoten *) calloc(1,sizeof(struct knoten));
        if (hilf == NULL)
                return hilf;
        hilf -> links = NULL;
        hilf -> rechts = NULL;
        hilf -> wert = wert;
        return hilf;
        }

insert_baum_000000(struct knoten **wurzel, int wert)
        {
        if (*wurzel == NULL)
                /* der baum ist noch leer */
                {
                *wurzel = new_knoten(wert);
                if (*wurzel == NULL)
                        return 1;
                return 0;
                }
        /* ist noch einzufuegen */
        }

print_baum_000000(struct knoten *wurzel)
        {
        if (wurzel != NULL)
                {
                printf(" %d ",wurzel->wert);
                }
        }

main()
{
        struct knoten *wurzel = NULL;
        if (insert_baum_000000(&wurzel,12))
                printf("irgendwas ist schief gelaufen\n");
        else
                print_baum_000000(wurzel);
}

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!