/*
 * Tree - implementacja biblioteki do prostej obslugi drzew binarnych
 * Drzewa przechowuja liczbe calkowita.
 * Zaimplementowane metody to tworzenie i usuwanie drzewa.
 * [c] piotao, 20060226, @manta
 */

#ifndef __BSTREE__
#define __BSTREE__

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

typedef struct tnode {
	int data;
	struct tnode* left;
	struct tnode* right;
} tnode;

typedef struct {
	int size;
	tnode* tree;
} Tree;


// prymitywna obsluga podstawowa

// tworzenie nowego, pustego noda z polami niezainicjowanymi
tnode* newNode(){
	return (tnode*) malloc( sizeof(tnode) );
}

// ustawianie pol noda, ktory juz istnieje
tnode* defNode( tnode* node, int liczba, tnode* lewy, tnode* prawy ){
	if(!node) node = newNode();
	node->data = liczba;
	node->left = lewy;
	node->right= prawy;
	return node;
}

// tworzenie nowego, pustego drzewa
Tree* newTree(){
	return (Tree*) malloc( sizeof(Tree) );
}

// obliczanie ilosci elementow poddrzewa t
int calcSize(tnode* t){
	int tmpsize = 1;
	if(t){
		if(t->left)  tmpsize += calcSize(t->left);
		if(t->right) tmpsize += calcSize(t->right);
	}
	return tmpsize;
}

// ustawianie korzenia w drzewie
Tree* defTree( Tree* T, tnode* node ){
	if(!T) T = newTree();
	T->tree = node;
	T->size = calcSize(T->tree);
	return T;
}

// obsluga drzewa

// dodawanie elementu, drzewo moze nie istniec lub byc puste.
// metoda nie jest przygotowana na powtorzenia w danych!
void insertData(Tree** T,int liczba){   // implementacja Tree-Insert
	if((*T) == NULL) (*T) = defTree(newTree(),defNode(newNode(),liczba,NULL,NULL));
	else{
		tnode* y = NULL;
		tnode* x = (*T)->tree;
		while(x){
			y = x;
			if( liczba < x->data ) x = x->left;
			else x = x->right;
		}
		tnode* p = defNode(newNode(),liczba,NULL,NULL);
		if(!y){
			(*T)->tree = p;
		}
		else{
			if(p->data < y->data){
				y->left = p;
			}
			else{
				y->right = p;
			}
		}
	}
}

// wypisanie wszystkich elementow poddrzewa t
// depth - przesuniecie od brzegu w celu pokazania struktury
void printNode(tnode* t, int depth){
	int i;
	if(t){
		for(i=0;i<depth;i++) printf("  ");
		printf("%c%i%c\n",(t->left)?'<':'[',t->data,(t->right)?'>':']');
		if(t->left) printNode(t->left,depth+1);
		if(t->right)printNode(t->right,depth+1);
	}
}

// wypisanie calego poddrzewa
void printTree(Tree* T){
	if(T){
		printNode(T->tree,0);
	}
}


#endif