/media/sda-magnetic/david/Dok-15-2023-11-27/fernuni-hagen/cs-i-ii/fsm/fsm/c-2020-11-08/binarytree.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 32

#define ERR_NO_MEM -1
#define STR_ERR_NO_MEM "Nicht genuegend Speicherplatz"

struct bin_tree {
    char v[N];
    struct bin_tree *r;
    struct bin_tree *l;
};

struct bin_tree *tree_insert (char *v, struct bin_tree *root) {
    if (root == NULL) {
        if ((root = malloc(sizeof(struct bin_tree))) == NULL) {
            perror (STR_ERR_NO_MEM);
            exit (ERR_NO_MEM);
        }
        strcpy (root->v, v);
        root->l = NULL;
        root->r = NULL;
        return root;
    }
    else {
        if (strcmp (v, root->v) <= 0) {
            if (root->l == NULL) {
                if ((root->l = malloc (sizeof(struct bin_tree))) == NULL) {
                    perror (STR_ERR_NO_MEM);
                    exit (ERR_NO_MEM);
                }
                strcpy (root->l->v, v);
                root->l->r = NULL;
                root->l->l = NULL;
                return root->l;
            }
            else 
                return tree_insert (v, root->l);
        }
        else {
            if (root->r == NULL) {
                if ((root->r = malloc (sizeof(struct bin_tree))) == NULL) {
                    perror (STR_ERR_NO_MEM);
                    exit (ERR_NO_MEM);
                }
                strcpy (root->r->v, v);
                root->r->r = NULL;
                root->r->l = NULL;
                return root->r;
            }
            else 
                return tree_insert (v, root->r);
        }
    }
}

struct bin_tree *tree_contents (char *v, struct bin_tree *root) {
    if (root == NULL)
        return NULL;
    if (strcmp (v, root->v) == 0)
        return root;
    else if (strcmp (v, root->v) < 0)
        return tree_contents (v, root->l);
    else if (strcmp (v, root->v) > 0)
        return tree_contents (v, root->r);
}

void tree_traverse (struct bin_tree *root) {
    if (root != NULL) {
        tree_traverse (root->l);
        printf ("%s\n", root->v);
        tree_traverse (root->r);
    }
}

int main (void) {
    struct bin_tree *root;
    
    root = tree_insert ("Heinrich", NULL);
    tree_insert ("Caesar", root);
    tree_insert ("Anton", root);
    tree_insert ("Xantippe", root);
    tree_insert ("Dora", root);
    tree_insert ("Kaufmann", root);
    tree_insert ("Anton", root);
    tree_insert ("Berta", root);
    
    tree_traverse (root);
    
    if (tree_contents ("Berta", root) != NULL)
        printf ("Berta gefunden\n");
    if (tree_contents ("Emil", root) == NULL)
        printf ("Emil nicht gefunden\n");
    
    
}