#include <stdio.h>
#include <stdbool.h>

typedef struct _noeud
{
	int valeur ;
	struct _noeud * fils_gauche;
	struct _noeud * fils_droite;
}noeud;

/* AUtre possibilité pour déclarer la structure
 * // Définition du type structuré
 * struct _noeud
 * {
 * 		int valeur ;
 * 		struct _noeud * fils_gauche ;
 * 		struct _noeud * fils_droite ;
 * };
 * //Alias
 * typedef struct _noeud noeud ;
 */

//allocation mémoire d'un maillon (noeud)
noeud* creer_noeud(int v){

	noeud * element = (noeud*)malloc(sizeof(noeud));
	element -> valeur = v;
	//initialisation des pointeurs gauche et droite
	element -> fils_gauche = NULL;
	element -> fils_droite = NULL;
	return element;
}

//asocier un noeud gauche
bool associer_fils_gauche(noeud* parent, noeud* enfant){
	bool ok = false;
	if(parent != NULL){
		/* vérifier si le parent n'a pas déjà de fils gauche et
		 l'enfant existe
		*/
		if(parent-> fils_gauche == NULL && enfant != NULL){
			parent -> fils_gauche = enfant;
		}
	}
	return ok;
}

//asocier un noeud droite
bool associer_fils_droite(noeud* parent, noeud* enfant){
	bool ok = false;
	if(parent != NULL){
		/* vérifier si le parent n'a pas déjà de fils droit et
		 l'enfant existe
		*/
		if(parent -> fils_droite == NULL && enfant != NULL){
			parent -> fils_droite = enfant;
		}
	}
	return ok;
}

bool est_feuille (noeud*  element){
	bool ok = false;

	if (element != NULL){
		if(element -> fils_gauche == NULL && element -> fils_droite == NULL){
			ok = true;
		}
	}
	return ok;
}

void exo1(){

	noeud* racine = creer_noeud(20);
	associer_fils_gauche(racine,creer_noeud(10));
	associer_fils_droite(racine,creer_noeud(15));
	est_feuille(15);
}


void affichage_prefixe(noeud * arbre){

	if (arbre != NULL){
		printf("%d \n",arbre -> valeur);
		affichage_prefixe(arbre ->fils_gauche);
		affichage_prefixe(arbre -> fils_droite);
	}
}

void affichage_infixe(noeud * arbre){

	if (arbre != NULL){
		affichage_infixe(arbre ->fils_gauche);
		printf("%d \n",arbre -> valeur);
		affichage_infixe(arbre -> fils_droite);
	}
}

void affichage_postfixe(noeud * arbre){

	if(arbre != NULL){
		affichage_postfixe(arbre -> fils_gauche);
		affichage_postfixe(arbre -> fils_droite);
		printf("%d \n", arbre -> valeur);
	}
}

void exo2(){

	noeud * racine = creer_noeud (12) ;

	// Sous - arbre de gauche
	noeud * n1 = creer_noeud (1) ;
	associer_fils_gauche (n1 , creer_noeud (91));
	associer_fils_droite (n1 , creer_noeud (67));

	// Sous - arbre de droite
	noeud * n7 = creer_noeud (7) ;
	noeud * n82 = creer_noeud (82) ;
	associer_fils_droite (n7 , n82);
	associer_fils_gauche (n82 , creer_noeud (61));

	// Assemblage final
	associer_fils_gauche (racine , n1);
	associer_fils_droite (racine , n7);
	affichage_prefixe(racine);
	printf("%d \n");
	affichage_infixe(racine);
	printf("%d \n");
	affichage_postfixe(racine);
}


int nombre_enfants(noeud * parent){
	int cpt = 0;
	if (parent != NULL){
		if(parent -> fils_gauche != NULL)
			cpt++;
		if(parent -> fils_droite != NULL)
			cpt++;
	}
	return cpt;
}

int nbr_elements(noeud * arbre){
	if (arbre == NULL)
		return 0;
	else
		return 1 + nbr_elements(arbre -> fils_gauche) + nbr_elements(arbre -> fils_droite);
}

int nombre_descendants(noeud * parent) {
	return nbr_elements(parent) - 1; //tous les éléments moins celui de la racine
}

int nombre_feuilles(noeud * parent){

	if (parent == NULL)
		return 0;
	else {
		if (est_feuille(parent))
			return 1;
		else
			return nombre_feuilles(parent -> fils_gauche) + nombre_feuilles(parent -> fils_droite);
	}
}


void exo4(){
}


int main(int argc, char **argv)
{
	//exo1();
	//exo2();
	//exo3();
	exo4();

	scanf("\n");
	return 0;
}