Aufgabe 13 (10 Programmierpunkte - Abgabe per email bis 18.6. 10.00 Uhr)
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 14 (4+2 Punkte)
Man gebe ein Beispiel eines AVL Baums an, bei dem beim Löschen eines geeigneten Knotens mindestens 4 Rotationen oder Doppelrotationen zum Wiederherstellen der AVL-Baumeigenschaft nötig sind. Beweis. (4 Punkte) Wie läßt sich das auf n Rotationen verallgemeinern? (2 Punkte)

Aufgabe 15 (6 Punkte)
Ist es in Bezug auf die Anzahl der Zeigerwechsel günstiger die Doppelrotation als gesonderte Funktion zu programmieren oder sie durch Aufruf zweier entsprechender Funktionen zu realisieren? Begründung.