#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;
}
