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

typedef struct node {
		int key;
		struct node * sin;
		struct node * dx;
	} nodo;

typedef nodo * albero;

void inseriscivalore (albero * tree, int chiave);
void visita (albero tree);
void visita_ampiezza (albero tree);

int stampalivello (albero tree, int limite_profondita, int profondita_corrente);
// funzione di supporto per la visita in ampiezza

int main () {

albero faggio = NULL;

inseriscivalore	(&faggio, 5);
inseriscivalore	(&faggio, 7);
inseriscivalore	(&faggio, 1);
inseriscivalore	(&faggio, 9);
inseriscivalore	(&faggio, 5);
inseriscivalore	(&faggio, 6);

printf ("\nbene, ecco la struttura dell'alberello...\n");
visita_ampiezza (faggio);

printf ("\n\nok, ora visito l'albero in ordine:\n");
visita (faggio);
}

void inseriscivalore (albero * tree, int chiave) {
if (*tree == NULL) {
	   *tree = (nodo *) malloc (sizeof (nodo));
	   (*tree)->key = chiave;
	   (*tree)->sin = (*tree)->dx = NULL; }

else if ((*tree)->key > chiave) inseriscivalore (& ((*tree)->sin), chiave);
else if ((*tree)->key < chiave) inseriscivalore (& ((*tree)->dx), chiave);
else printf (" *** ERRORE: la chiave %d e' gia' presente, non inserisco\n", chiave
	);
}

void visita (albero tree) {
if (tree == NULL) return;
visita (tree->sin);
printf("%d ",tree->key);
visita (tree->dx);
}


/*
nota: per la visita in ampiezza di solito si usa in supporto una coda 
(struttura FIFO, il primo a entrare è il primo servito).
In pratica, prima di stampare ogni nodo, i suoi figli vengono inseriti nella coda. 
I nodi da stampare (ed espandere) vengono poi estratti dalla coda stessa: 
in questo modo si riesce a sfuggire alla ricorsione che, per sua natura, 
tende a visitare l'albero in profondità.

Io ho voluto sperimentare una tecnica diversa che visita, per così dire, ad 
approfondimento iterativo: la funzione si appoggia a una procedura di supporto che
stampa il (solo) livello i-esimo. La cosa difficile è capire quando l'albero è finito...
riuscite a comprendere come funziona il codice della funzione "stampalivello"?
*/
void visita_ampiezza (albero tree) {
int finito = 0;
int depth = 0;

while (!finito) {
	finito = stampalivello (tree, depth, 0);
	printf ("\n");
	// il valore restituito vale 1 se a quel livello di profondita' trovo solo NULL
	depth++; }
}

int stampalivello (albero tree, int limite_profondita, int profondita_corrente) {
int ris1, ris2;

if (tree == NULL) return 1; // esco dalla ricorsione e ho finito
if (limite_profondita == profondita_corrente) {
	printf("%d ", tree->key);
	return 0;
	}  // qui esco dalla ricorsione ma NON ho finito

/*
// non posso scrivere cosi' perche' l'and e' cortocircuitato
return stampalivello (tree->sin, limite_profondita, profondita_corrente+1) &&
		    stampalivello (tree->dx, limite_profondita, profondita_corrente+1);
*/

ris1 =	stampalivello (tree->sin, limite_profondita, profondita_corrente+1);
ris2 =  stampalivello (tree->dx, limite_profondita, profondita_corrente+1);
return ris1 && ris2;
// chiamo ricorsivamente, ho finito solo se entrambi i figli hanno finito
}