#include "baum.h"

//Speicher fuer ein neues Element reservieren
//und den Wert setzen
struct btree * create_element( int value ) {
	struct btree *tree = (struct btree *) malloc(sizeof(struct btree));
	if( tree == NULL ) {
		printf("COULD NOT ALLOC MEMORY!\n");
		exit(1);
	}
	else {
		tree->value = value;
		tree->left = NULL;
		tree->right = NULL;
		return tree;
	}
	
}

/*
 * Uebergabe erfolgt durch **root, 
 * da der Zeiger *root veraenderbar sein soll!
 * => *root = element;
 *
 * 
 * Gibt 1 bei erfolg und 0 bei fehler zurueck
*/
int put ( struct btree **root, struct btree *element ) {
	//ROOT ELEMENT ONLY!
	if( *root == NULL) {
		*root = element;
		return 1;		
	}
	
	if( element->value == (*root)->value ){
		/* value ist schon vorhanden */
		return 0;
	}
	else if( element->value < (*root)->value) {
		//Falls kein Kind vorhanden hier einfuegen
		if( (*root)->left == NULL ) {
			(*root)->left = element;
			return 1;
		}
		//Weiter im linken Ast suchen
		else {
			return put( &((*root)->left), element );
		}
	}
	else{
		//Falls kein Kind vorhanden hier einfuegen
		if( (*root)->right == NULL ) {
			(*root)->right = element;
			return 1;
		}
		//Weiter im rechten Ast suchen
		else {
			return put( &((*root)->right), element );
		}
	}
}
/*
 * Ausgabe als horizontaler Baum  
*/
void print(struct btree *tree) {
	//Variable bleibt ueber die Lebenszeit des Funktionsaufrufes hinaus bestehen
	static int level = 0;
	
	if (tree == NULL) {
		return;
	}
	//Ebene erhoehen
	level++;
	//Ausgabe
	//Je tiefer desto weiter rechts
	//=> %*d, das * erlaubt eine Variable angabe der Breite der Ausgabe
	printf("%*d\n", (level*5), tree->value);
	//Erst rechts, dann links
	if (tree->right != NULL) {
		print(tree->right);
	}
	if (tree->left != NULL) {
		print(tree->left);
	}
	//Eine Ebene runter
	level--;
}

void free_tree( struct btree *tree ) {
	if (tree == NULL) {
		return;
	}
	
	if (tree->right != NULL) {
		free_tree(tree->right);
	}
	if (tree->left != NULL) {
		free_tree(tree->left);
	}
	
	free(tree);	
}

int remove_element(struct btree **tree, int value) {
	struct btree *tmp;
	
	if( tree == NULL) {
		return 0;		
	}
	
	//gefunden
	if( value == (*tree)->value ) {
		if( ((*tree)->left == NULL) && ((*tree)->right == NULL) ) {
			free((*tree));
			(*tree) = NULL;
		}
		else if( ((*tree)->left == NULL) && ((*tree)->right != NULL) ) {
			tmp = (*tree)->right;
			free((*tree));
			(*tree) = tmp;
			
		}
		else if( ((*tree)->left != NULL) && ((*tree)->right == NULL) ) {
			tmp = (*tree)->left;
			free((*tree));
			(*tree) = tmp;
			
		}
		else {
			//Den kleinsten Wert im rechten Teilbaum suchen
			//und dessen Elternknoten merken!
			struct btree *parent = (*tree);
			tmp = (*tree)->right;
			while( 1 ) {
				if(tmp->left == NULL) {
					break;
				}
				else {
					parent = tmp;
					tmp = tmp->left;
				}
			}
			
			tmp->right = (*tree)->right;
			tmp->left = (*tree)->left;
			
			free((*tree));
			(*tree) = tmp;
			
			parent->left = NULL;			
		}
		return 1;
	}
		
	else if( value < (*tree)->value ) {
		return remove_element( (&(*tree)->left), value );
	}
	else {
		return remove_element( &((*tree)->right), value );
	}
}