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

typedef struct node_s
{
    char songtitle[256], interpreter[256];
    struct node_s *parent, *left, * right;
} node_t;

node_t *create_node(char songtitle[], char interpreter[])
{
    node_t *new;
    if(!(new=calloc(1,sizeof(node_t))))
    {
        fprintf(stderr,"Fehler bei Speicherallozierung!\n");
        exit(-1);
    }
    strcpy(new->songtitle,songtitle);
    strcpy(new->interpreter,interpreter);
    new->parent=0;
    new->left=0;
    new->right=0;
    printf("Knoten erstellen: %s %s\n",new->songtitle,new->interpreter);
    return new;
}

node_t *insert_node(node_t *rootnode, char songtitle[], char interpreter[])
{
    node_t *new=create_node(songtitle,interpreter);
    if(rootnode==0)
        return new;
    else
    {
        if(strcmp(new->songtitle,rootnode->songtitle)<=0)
            rootnode->left=insert_node(rootnode->left,songtitle,interpreter);
        else
            rootnode->right=insert_node(rootnode->right,songtitle,interpreter);
    }
    return rootnode;
}

void print(node_t *tree, long indent) {
    long i;
    if(tree->right != NULL)
        print(tree->right, indent + 1);
    for (i = 0; i < indent; ++i)
        printf("  ");
    printf("%s: %s\n", tree->interpreter, tree->songtitle);
    if(tree->left != NULL)
        print(tree->left, indent + 1);
}

void print_asked(node_t *tree) {
    printf("--- Tree ---\n");
    print(tree, 0);
    printf("--- ---\n");
}

void destroy_nodes(node_t *node)
{
    if(node->left)
        destroy_nodes(node->left);
    if(node->right)
        destroy_nodes(node->right);
    free(node);
    return;
}

node_t *search_node(node_t *rootnode, char songtitle[])
{
    if(!(strcmp(songtitle,rootnode->songtitle)))
        return rootnode;
    if((strcmp(songtitle,rootnode->songtitle)<=0)&&(rootnode->left!=0))
       rootnode=search_node(rootnode->left,songtitle);
    else
    {
        if(rootnode->right!=0)
            search_node(rootnode->right,songtitle);
        else
        {
            fprintf(stderr,"Knoten existiert nicht!\n");
            return 0;
        }
    }
    return rootnode;
}
long count_nodes_with_interpreter(node_t *rootnode, char interpreter[]) {
    long num = 0;
    if(strcmp(rootnode->interpreter, interpreter) == 0)
        num++;
    if(rootnode->left != NULL)
        num += count_nodes_with_interpreter(rootnode->left, interpreter);
    if(rootnode->right != NULL)
        num += count_nodes_with_interpreter(rootnode->right, interpreter);
    return num;
}

long count_nodes(node_t *rootnode)
{
    long num=1;
    if(rootnode->left!=0)
        num+=count_nodes(rootnode->left);
    if(rootnode->right!=0)
        num+=count_nodes(rootnode->right);
    return num;
}

long count_nodes_with_interpreter(node_t *rootnode, char interpreter[])
{
    long num=0;
    if((strcmp(rootnode->interpreter,interpreter))==0)
        num++;
    if(rootnode->left!=0)
    {
        num=count_nodes_with_interpreter(rootnode->left,interpreter);
        if((strcmp(rootnode->interpreter,interpreter))==0)
            num++;
    }
    if(rootnode->right!=0)
    {
        num=count_nodes_with_interpreter(rootnode->right,interpreter);
        if((strcmp(rootnode->interpreter,interpreter))==0)
            num++;
    }
    return num;
}

int main()
{
    node_t *node=0,*search=0;
    printf("Baum!\n");
    node=insert_node(node,"abc","abc");
    print(node);
    node=insert_node(node,"def","def");
    print(node);
    node=insert_node(node,"abc","ghi");
    print(node);
    node=insert_node(node,"jkl","abc");
    print(node);
    node=insert_node(node,"jjk","abc");
    print(node);
    node=insert_node(node,"bbc","abc");
    print(node);
    search=search_node(node,"bbc");
    if(search!=0)
        printf("\nbbc gefunden!\n");
    printf("Knotenanzahl: %ld\n",count_nodes(node));
    printf("Kontenanzahl mit Interpreter abc: %ld\n",count_nodes_with_interpreter(node,"abc"));
    destroy_nodes(node);
    return 0;
}