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

typedef struct node {
    char value;

    struct node *left_c;
    struct node *righ_c;
} nodes;

nodes *init() {
    nodes *nouv = malloc(sizeof(nodes));
    nouv->value = 'E';
    nouv->left_c = NULL;
    nouv->righ_c = NULL;
    return nouv;
}

void addchild(nodes *racine, int x, char value) {
    nodes *nouv = malloc(sizeof(nodes));
    nouv->value = value;
    nouv->left_c = NULL;
    nouv->righ_c =NULL;
    if (x==0) {
        racine->left_c=nouv;
    }
    else {
        racine->righ_c=nouv;
    }
}

int mystrlen(char *str) {
    int k =0;
    while (str[k]!='\0')
        k++;

    return k;
}

char *suppr(char *str){
    char *s = malloc(sizeof(char) *(mystrlen(str)));
    s = strncpy(s, str, mystrlen(str));
    s[(mystrlen(str))] = '\0';
    return s;
}

void printnode(nodes *racine, char *chemin, int nb) {



    int hauteur= strlen(chemin);

    if (nb == 0) {
        printf("\t %c", racine->value);
        return;
    }

    char *nchemin = malloc(sizeof(char) *(strlen(chemin)+1));
    nchemin = strcpy(nchemin, chemin);


    if (hauteur == nb)
        printf("\t %c", racine->value);
 //   else
   //     printf(">%d  ", hauteur);


    if (racine->left_c !=NULL){
        nchemin = strcat(nchemin, "0");
        printnode(racine->left_c, nchemin, nb);
        nchemin = suppr(nchemin);
    }
    if (racine->righ_c !=NULL) {
        nchemin = strcat(nchemin, "1");
        printnode(racine->righ_c, nchemin, nb);
        nchemin = suppr(nchemin);
    }

}


nodes *find(nodes *racine, char *str) {
    nodes *tmp =racine;
    int k = 0;
            printf("début du find()\n");
    while (str[k]!='\0') {
            printf("%c\n", tmp->value);

        if (str[k]=='0' && tmp->left_c !=NULL)
            tmp= tmp->left_c;

        else if (str[k]=='1' && tmp->righ_c !=NULL)
            tmp= tmp->righ_c;

        else
        {
            printf("chemin non valide\n");
            return NULL;
        }
        k++;
    }
    return tmp;
}

void addmore(nodes *racine, int x)
{

    addchild(racine, 0, '0');
    addchild(racine, 1, '1');
    if (x>1){
    addmore(racine->left_c, x-1);
    addmore(racine->righ_c, x-1);
    }

}


void occurrence(int *no, char *occ, int *hauteur, nodes *racine) {
    *no = 1;
    *hauteur = 0;
    int k = 0;
    nodes *temp = racine;

    if (occ[k]=='E'){
        return;
    }

    while (occ[k]!='\0') {
        if (occ[k]=='0') {
            temp = temp->left_c;
            *no = *no*2;
        }
        if (occ[k]=='1') {
            temp=temp->righ_c;
            *no=(*no*2)+1;
        }
        *hauteur = *hauteur+1;
        k++;
    }
}



int main()
{
    nodes *racine;
    nodes *tmp1;
    nodes *tmp2;
    int no =1;
    int *pno= &no;
    char occ[] ="E";
    int hauteur;
    char *chemin = malloc(sizeof(char)*50);
    chemin[0] = 'E';

    racine = init();

    addmore(racine, 10);


    int k;
    for (k=0; k<10; k++)
    {
        printf("k = %d ", k);
        printnode(racine, chemin, k);
        printf("\n");
    }

    return 0;
}