Die Aufgaben sollen in Zweiergruppen bearbeitet werden. Dreiergruppen sind nicht zulässig
Jede Aufgabe soll  auf einem Extrablatt bearbeitet werden. Bitte auf jedem Blatt Name/Matrikelnummer notieren.
 

Aufgabe 13 (10 Punkte Programmieraufgabe per email bis 7.6.01)
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)
        { /*  ist noch zu erweitern */
        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 14  (4 +2 Punkte)
Formulieren Sie in Pseudocode einen Algorithmus zur Ausgabe eines Intervalls. Der Algorithmus soll nicht rekursiv sein, sondern Sie verwalten den  nötogen lwr 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.  Beim Aufruf von werden zwei Parameter  übergeben, diese geben die untere und obere Intervallgrenze  an

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!