/media/sda-magnetic/david/Extern-Magnetic-2022-06-29/Extern01/Dokumente-2020-11-16/disk10-ab-2020-01-10/02-debian-pc2-work/informatik/c-2020-11-08/binarytreeavr2.c

#define __heap_end 2048

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <avr/io.h>
#include "lcd-routines.h"

#define N 32

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

char out_str[64];

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) 
            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) 
                    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) 
                    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);
        sprintf (out_str, "%s ", root->v);
        lcd_string(out_str);
        tree_traverse (root->r);
    }
}

int main (void) {
    struct bin_tree *root;
    
    lcd_init();  
    lcd_setcursor( 0, 2 );
    
    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) {
        sprintf (out_str, "Berta gefunden\n");
        lcd_string(out_str);
    }
    if (tree_contents ("Emil", root) == NULL) {
        sprintf (out_str, "Emil nicht gefunden\n");
        lcd_string(out_str);
    }*/
    
    
}