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

#define N 100

typedef struct cvor{
	int br;
	struct cvor *l;
	struct cvor *d;
} CVOR;

typedef struct red{
	CVOR *el;
	struct red *sl;
} RED;

CVOR* napravi(int br);
RED* napravir(CVOR *el);
void ubaci_u_drvo(CVOR **koren, int br);
void ispisi(CVOR *koren);
void obrisi(CVOR **koren);
void izbacipoc(RED **pocr, RED **krajr);
void dodajkraj(RED **pocr, RED **krajr, CVOR *el);

int main(){
	int i;
	CVOR *koren=NULL;
	RED *pocr=NULL;
	RED *krajr=NULL;
	int br;
	for(i=0; i<10; i++){
		br=(int)(rand()*1.0/RAND_MAX*N);
		ubaci_u_drvo(&koren,br);
		printf("Dodajem cvor %d\n",br);
	}
	dodajkraj(&pocr,&krajr,koren);
	while(pocr!=NULL){
		if(pocr->el->l!=NULL)
			dodajkraj(&pocr,&krajr,pocr->el->l);
		if(pocr->el->d!=NULL)
			dodajkraj(&pocr,&krajr,pocr->el->d);
		printf("%d\n",pocr->el->br);
		izbacipoc(&pocr,&krajr);	
	}
	obrisi(&koren);
}

CVOR* napravi(int br){
	CVOR* novi=(CVOR*)malloc(sizeof(CVOR));
	if(novi==NULL)
		exit(EXIT_FAILURE);
	novi->br=br;
	novi->l=NULL;
	novi->d=NULL;
	return novi;
}

RED* napravir(CVOR *el){
	RED* novi=(RED*)malloc(sizeof(RED));
	if(novi==NULL)
		exit(EXIT_FAILURE);
	novi->el=el;
	novi->sl=NULL;
}

void ubaci_u_drvo(CVOR **koren, int br){
	CVOR *pom;
	CVOR *novi;
	if(*koren==NULL){
		*koren=napravi(br);
	}else{
		pom=*koren;
		novi=napravi(br);
		while(1){
			if(br>pom->br){
				if(pom->d==NULL){
					pom->d=novi;
					return;
				}else
					pom=pom->d;
			}else{
				if(pom->l==NULL){
					pom->l=novi;
					return;
				}else
					pom=pom->l;
			}
		} 
	}
}

void ispisi(CVOR *koren){
	if(koren==NULL){
		printf("\n");
		return;
	}
	ispisi(koren->l);
	printf("%d\t",koren->br);
	ispisi(koren->d);
}

void obrisi(CVOR **koren){
	if(*koren==NULL)
		return;
	obrisi(&(*koren)->l);
	obrisi(&(*koren)->d);
	free(*koren);
	*koren=NULL;
}

void izbacipoc(RED **pocr, RED **krajr){
	RED *pom;
	if(*pocr==NULL)
		return;
	if(*pocr==*krajr){
		free(*pocr);
		*pocr=NULL;
		*krajr=NULL;	
	}else{
		pom=(*pocr)->sl;
		free(*pocr);
		*pocr=pom;
	}
}

void dodajkraj(RED **pocr, RED **krajr, CVOR *el){
	if(*pocr==NULL){
		*pocr=napravir(el);
		*krajr=*pocr;
	}else{
		(*krajr)->sl=napravir(el);
		*krajr=(*krajr)->sl;
	}
}