Lösungsbeispiel zu Blatt 7 (Aufgabe 11)

tree.c

/*
 *      tree.c  - Beispielprogramm fuer binaere Baeume
 *
 *      Synopsis: tree
 *
 *      Erzeugen eines ausgeglichenen binaeren Baums mit N Datensaetzen,
 *      die in sortierter Folge aus der Standardeingabe gelesen werden,
 *      wobei N eine fest vorgegebene Zahl darstellt;
 *
 *      Ausgabe der Baumstruktur auf die Standardausgabe;
 *
 *      Bereitstellung von Funktionen zur Ausgabe aller Datensaetze
 *      in inorder-, preorder- und postorder-Reihenfolge;
 *
 *      Lesen und Einfuegen weiterer Datensaetze aus der Standardeingabe
 *      bis zum Ende der Eingabe;
 *
 *      Schreiben der Daten in die Standardausgabe.
 *
 *      Martin Hasch, Universitaet Ulm, Januar 1997.
 */

#include        <stdio.h>
#include        <malloc.h>

#define TREESIZE        5       /* N */

typedef struct tree {
        int t_key;
        struct tree *t_left, *t_right;
} *Tree;

/*
 *      Allokation eines neuen Knotens ohne Initialisierung.
 *      Resultat ist der neue Knoten.  Erfolg wird garantiert.
 */
static Tree new_tree(void)
{
        Tree result;

        result = (Tree) malloc( sizeof(struct tree) );
        if ( !result ) {
                fprintf(stderr, "out of memory!\n");
                exit(2);
        }
        return result;
}

/*
 *      Ausgabe eines Datensatzes.
 */
static void print_element(Tree element)
{
        printf("%d\n", element->t_key);
}

/*
 *      Lesen eines Datensatzes.  Resultat ist 1 bei Erfolg, sonst 0.
 */
static int read_element(int *key)
{
        return scanf("%d", key) == 1;
}

/*
 *      Einlesen eines Baumes mit (size) Elementen.
 *      Korrekte Syntax und Reihenfolge wird vorausgesetzt.
 */
void buildTree(Tree *tree, int size)
{
        Tree this;

        if ( size <= 0 ) {
                this = NULL;
        } else {
                this = new_tree();
                buildTree(&this->t_left, size/2);
                if ( !read_element(&this->t_key) ) {
                        fprintf(stderr, "number expected!\n");
                        exit(1);
                }
                buildTree(&this->t_right, (size-1)/2);
        }
        *tree = this;
}

/*
 *      Ausgabe der Struktur eines Baumes in zweidimensionaler Form.
 */
void printTree(Tree tree, int level)
{
        if ( tree != NULL ) {
                printTree(tree->t_left, level+1);
                printf("%*s%d\n", level*4, "", tree->t_key);
                printTree(tree->t_right, level+1);
        }
}

/*
 *      Ausgabe aller Datensaetze eines Baumes in inorder-Reihenfolge.
 */
void inorder(Tree tree)
{
        if ( tree != NULL ) {
                inorder(tree->t_left);
                print_element(tree);
                inorder(tree->t_right);
        }
}

/*
 *      Ausgabe aller Datensaetze eines Baumes in preorder-Reihenfolge.
 */
void preorder(Tree tree)
{
        if ( tree != NULL ) {
                print_element(tree);
                preorder(tree->t_left);
                preorder(tree->t_right);
        }
}

/*
 *      Ausgabe aller Datensaetze eines Baumes in postorder-Reihenfolge.
 */
void postorder(Tree tree)
{
        if ( tree != NULL ) {
                postorder(tree->t_left);
                postorder(tree->t_right);
                print_element(tree);
        }
}

/*
 *      Suche eines Datensatzes mit Schluessel (key) in einem Baum;
 *      Einfuegen, falls noch nicht vorhanden.
 *      Resultat ist ein Zeiger auf den Datensatz.
 */
Tree * insert(Tree *tree, int key)
{
        while ( *tree != NULL ) {
                if ( key < (*tree)->t_key )
                        tree = &(*tree)->t_left;
                else if ( key > (*tree)->t_key )
                        tree = &(*tree)->t_right;
                else
                        return tree;
        }
        *tree = new_tree();
        (*tree)->t_key = key;
        (*tree)->t_left = (*tree)->t_right = NULL;
        return tree;
}

/*
 *      Testprogramm.
 */
int main(void)
{
        static Tree data;
        int key;

        buildTree(&data, TREESIZE);
        printTree(data, 0);

        while ( read_element(&key) ) {
                (void) insert(&data, key);
        }
        printf("inorder:\n");
        inorder(data);
        printf("preorder:\n");
        preorder(data);
        printf("postorder:\n");
        postorder(data);
        return 0;
}