//CHAZAL Baptiste L2 C


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


//Structure du noeud :
typedef struct node
{
    int data ;
    struct node *left, *right;
} node;
typedef node *tree ;


//Prototypes :
tree new_node(int) ;
void new_full_tree(tree*, int) ;
void print_tree(tree) ;
unsigned nr_Leaves (tree t) ;


//Fonction main :
int main()
{
    tree arbre = NULL ;
    int profondeur = 1 ;

    //Initialisation de l'aléatoire :
    srand(time(NULL));

    //Création de l'arbre :
    printf ("\tCreation de l'arbre.\n") ;
    do
    {
        new_full_tree(&arbre, profondeur) ;
        profondeur++ ;
    } while (rand()%2 == 1) ;

    //Affichage de l'arbre :
    printf("\nAffichage de l'arbre :\n");
    print_tree(arbre) ;

    //Calcul et affichage du nombre de feuilles de l'arbre :
    printf("\nIl y a %d feuilles dans cet arbre.\n", nr_Leaves(arbre)) ;

    return 0 ;
}


//Creer un noeud initialise sur NULL pour les enfants et la profondeur du noeud pour la donnee :
tree new_node(int e)
{
    tree arbre = (tree)malloc(sizeof(node)) ;
    if(arbre==NULL) //On test le malloc
    {
        printf("Segmentation fault.\n");
        return NULL;
    }

    //On initialise les champs
    arbre->data = e;
    arbre->left = NULL;
    arbre->right = NULL;

    return arbre ;
}


//Ajoute un element dans un arbre binaire :
void new_full_tree(tree *pt, int profondeur)
{
    tree arbre = *pt;

    if(arbre==NULL) //Si le noeud est vide on le creer
    {
        *pt = new_node(profondeur);
    }
    else
    {
        new_full_tree(&(arbre->left), profondeur);
        new_full_tree(&(arbre->right), profondeur);
    }
}


//Affiche un arbre :
void print_tree(tree t)
{
    if(!t) {printf(".");}
    else {
        if(!(t->left || t->right)) {
            printf("%d", t->data);
                                    }
        else {
            printf("(%d, l:", t->data);
            print_tree(t->left);
            printf(", r:");
            print_tree(t->right);
            printf(")");
            }
        }
}


//Calcul le nombre de feuilles d'un arbre :
unsigned nr_Leaves (tree t)
{
    if (t==NULL) {return 0 ;}
    else if (t->left==NULL && t->right==NULL) return 1 ;
    else return (nr_Leaves(t->left)+nr_Leaves(t->right)) ;
}