/* Algorithmen und Datenstrukturen Uebung 5 */

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


// Globale Variablen und Typdefinitionen

typedef struct node_ {
   int key; 
   int bf;
   char *data;
   struct node_ *left; 
   struct node_ *right;
} node;

typedef struct biTree_ {
  int size;
  node *root;
} biTree;


// Funktionsprototypen

node *insertNode(node *, int , char *,node *, biTree *);
node *insert(biTree *, int, char *);
void printTreeInline (node *);
void printTreeLevelOrder (node *); 
node *lookup (node *, int);
int treeDepth (node *);
node *left2;   //Hilfszeiger
node *right2;  //Hilfszeiger
node *grandchild;

// Funktionen

// Funktion insertNode: siehe Vorlesungsfolien
node *insertNode(node *start, int key, char *data, node *parent, biTree *t) 
{
	node *newNode;
	if (start == NULL) {
	newNode = malloc(sizeof(node));
	if (newNode != NULL) {
	newNode->data = data;
	newNode->key = key;
	newNode->right = newNode->left = NULL;
	newNode->bf = 0;
	}
	return newNode;
	}
	if (key < start->key) {
	newNode = insertNode(start->left, key, data, start, t);
	if (start->left == NULL)
	start->left = newNode;
	}
	else {
	newNode = insertNode(start->right, key, data, start, t);
	if (start->right == NULL)
	start->right = newNode;
	}
	
	//Balance Faktor berechnen
	start->bf = treeDepth(start->left) - treeDepth(start->right);

	//Unterscheidung der 4 F&Atilde;&curren;lle, rotieren und Balance Faktor korrigieren
	if(start->bf == +2){
		if(start->left->bf== +1){
			//LL
			left2 = start->left;
			start->left= left2->right;
			left2->right=start;
			if(parent == NULL){
				t->root=left2;
			}else{
			if(start == parent->left){
				parent->left=left2;
			}
			if(start == parent->right){
				parent->right=left2;
			}
			}
			start->bf=NULL;
			left2->bf=NULL;
		}else{
			//LR
			left2 = start->left;
			grandchild=left2->right;
			left2->right=grandchild->left;
			grandchild->left=left2;
			start->left=grandchild->right;
			grandchild->right=start;

			if(parent == NULL){
				t->root=grandchild;
			}else{
			if(start == parent->left){
				parent->left=grandchild;
			}
			if(start == parent->right){
				parent->right=grandchild;
			}
		  }
			if(grandchild->bf == +1){
				start->bf=-1;
				left2->bf=0;
			}
			if(grandchild->bf == 0){
				start->bf=0;
				left2->bf=0;
			}
			if(grandchild->bf == -1){
				start->bf=0;
				left2->bf=+1;
			}
			grandchild->bf=0;
		}
	}

	if(start->bf== -2){
		if(start->right->bf== -1){
			//RR
			right2 = start->right;
			start->right= right2->left;
			right2->left=start;

			if(parent == NULL){
				t->root=right2;
			}else{
			if(start == parent->left){
				parent->left=right2;
			}
			if(start == parent->right){
				parent->right=right2;
		   }
		 }
		 start->bf=NULL;
		 right2->bf=NULL;
		}else{
			//RL
			right2 = start->right;
			grandchild=right2->left;
			right2->left=grandchild->right;
			grandchild->right=right2;
			start->right=grandchild->left;
			grandchild->left=start;

			if(parent == NULL){
				t->root=grandchild;
			}else{
			if(start == parent->left){
				parent->left=grandchild;
			}
			if(start == parent->right){
				parent->right=grandchild;
			}
		}  
	  }
	}

	return newNode;
}

// Funktion insert: siehe Vorlesungsfolien
node *insert(biTree *t, int key, char *data) 
{
	node *newNode;
	newNode = insertNode(t->root, key, data, NULL, t);
	if (t->root == NULL) t->root = newNode;
	if (newNode != NULL) t->size++;
	return newNode;
}

// Rekursive Funktion zum Ausgeben des Baumes in Inline-Notation
void printTreeInline (node *start) 
{
	if(start!=NULL){
	printTreeInline(start->left);
	printf("Daten: %d
",start->key);
	printTreeInline(start->right);
	}
}

// Funktion zum ebenenweise Ausgeben des Baumes
void printTreeLevelOrder (node *start) 
{

}

// Suchen eines Knotens anhand des Keys
node *lookup (node *start, int key) 
{
	if (start == NULL) {
	return NULL; // Knoten nicht gefunden
	}
	if (key == start->key) {
	return start; // Knoten wurde gefunden
	}
	if (key < start->key) {
	return lookup(start->left, key);
	}
	else {
	return lookup(start->right, key);
	}
}

int treeDepth (node *start) 
{
	if (start == NULL) 
	{
	return 0;
	}
	else {
	return 1 + max(treeDepth(start->left),
	treeDepth(start->right));
	}
}


// Hauptprogramm

int main(void)
{
	// Variablen fuer den Baum anlegen
	int i;
	int x;
	int y;
	biTree tree;
	node *node;
	char* data;
	int key=0;
	int start=0;
	tree.root=NULL;
	tree.size=0;
	i=0;
	
	
	// Einlesen mehrerer Datensaetze von der Tastur
	// und Einf&Atilde;&frac14;gen in den Baum mittels insert()

	printf("Wieviele Datensaetze moechten sie erfassen? 
");
	scanf("%d",&y);

	for(x=1;x<=y;x++){
		printf("Bitte geben Sie die Personalnummer ein: 
");
		scanf("%d",&key);
		getchar();

		node=lookup(tree.root,key);
		if(node!=NULL){
			printf("Bereits vorhanden! 
");
			x--;
		}
		else
		{
		data = (char*) malloc(30);
		printf("Bitte geben Sie den Namen ein: 
");
		gets(data);
		
		insert(&tree, key , data);
		}
	}
	
	// Ausgabe des Baumes in Inline-Notation
	printTreeInline(tree.root);
	
	// Ausgabe der Baumtiefe
	i=treeDepth (tree.root);
	printf("Baumtiefe: %d
",i);
	
	// Ausgabe von Minimum- und Maximum-Key
	
	
	// Ausgabe des Baumes in Levelorder
	printTreeLevelOrder(start);
	
	// Suchen nach Datensaetzen (laeuft in einer Schleife)
	// wie in der Aufgabenstellung beschrieben
	while(1){
		printf("Bitte geben Sie die nach der zu suchenden Personalnummer ein: 
");
		scanf("%d",&key);
		getchar();
		
		if(key==0){
			break;
		 }

		node=lookup(tree.root,key);
		
		if(node==NULL){
		printf("Personaldaten nicht gefunden! 
");
		}
		else{
			printf("%s
",node->data);
		}
	}
	return 0;
}