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

//############## Struktur und Funktionen für eine einfache verkettete Liste ##############
typedef struct NODE {
	int elem;
	struct NODE *next;
} node;

node *anfuegen(node *akt, int elem){
	node *neu=(node *)malloc(sizeof(node));
	neu->next=NULL;
	neu->elem=elem;
	akt->next=neu;
	return neu;
}

void loesche_liste(node *head){
	node *h2, *h=head->next;
	while(h!=NULL){
		h2=h->next;
		free(h);
		h=h2;
	}
}

void print_liste(node *head){
	node *h=head;
	printf("Head->");
	while(h->next!=NULL){
		h=h->next;
		printf("%d->", h->elem);
	}
	printf("NULL\n\n");
}
//########################################################################################


//################## Struktur und Funktionen eines binären Suchbaumes ####################
typedef struct LEAF {
	int elem;
	struct LEAF *ls;
	struct LEAF *rs;
} leaf;

leaf *einfuegen(leaf *knoten, int elem){
	if(knoten==NULL){
		leaf *blatt=(leaf *)malloc(sizeof(leaf));
		blatt->ls=blatt->rs=NULL;
		blatt->elem=elem;
		return blatt;
	}

	if(elem<=knoten->elem)
		knoten->ls=einfuegen(knoten->ls, elem);
	else
		knoten->rs=einfuegen(knoten->rs, elem);
	return knoten;
}

void loesche_baum(leaf *knoten){
	if(knoten->ls!=NULL)
		loesche_baum(knoten->ls);
	if(knoten->rs!=NULL)
		loesche_baum(knoten->rs);
	free(knoten);
}

void print_inorder(leaf *knoten){
	if(knoten->ls!=NULL)
		print_inorder(knoten->ls);
	printf("%d->", knoten->elem);
	if(knoten->rs!=NULL)
		print_inorder(knoten->rs);
}

void print_preorder(leaf *knoten){
	printf("%d->", knoten->elem);
	if(knoten->ls!=NULL)
		print_preorder(knoten->ls);
	if(knoten->rs!=NULL)
		print_preorder(knoten->rs);
}

void print_postorder(leaf *knoten){
	if(knoten->ls!=NULL)
		print_postorder(knoten->ls);
	if(knoten->rs!=NULL)
		print_postorder(knoten->rs);
	printf("%d->", knoten->elem);
}
//########################################################################################


int main(void){
	int zzahl, i;
	node *akt, *head=(node *)malloc(sizeof(node));
	leaf *wurzel;
	head->next=NULL;
	head->elem=0;
	srand(time(NULL));

	//#################### verkettete Liste erzeugen und ausgeben ####################
	zzahl=rand()%20;
	akt=head;
	for(i=0; i<zzahl; i++)
		akt=anfuegen(akt, rand()%100+1);
	printf("\nAusgabe der verketteten Liste:\n");
	print_liste(head);

	//##################### bin. Suchbaum aus der Liste erzeugen #####################
	if(head->next!=NULL)
		wurzel=einfuegen(NULL, head->next->elem);
	akt=head->next;
	while(akt->next!=NULL){
		akt=akt->next;
		(void *)einfuegen(wurzel, akt->elem);
	}
	printf("Baum inorder ausgegeben: ");
	print_inorder(wurzel);
	printf("\b\b  \n");
	printf("Baum preorder ausgegeben: ");
	print_preorder(wurzel);
	printf("\b\b  \n");
	printf("Baum postorder ausgegeben: ");
	print_postorder(wurzel);
	printf("\b\b  \n\n");

	loesche_baum(wurzel);
	loesche_liste(head);
	free(head);
	return 0;
}