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

/* Type des noeuds d'un arbre. */
typedef struct noeud {
  char info;
  struct noeud* filsGauche;  
  struct noeud* filsDroit;  
} Noeud, *Arbre;


typedef struct table {
  char *t;
  int n;
} Table;

/* Retourne la plus grande des deux valeurs. */
int max(int a, int b) {
  if (a>b)
    return a;
  return b;
}

/* Retourne 1 si a est une feuille, 0 sinon. */
int estFeuille(Arbre a) {
  return !(a->filsGauche || a->filsDroit);
}

/* Retourne la hauteur de l'arbre. Cette fonction suppose que a est non nul. */
int hauteurNN(Arbre a) {
  int g=0, d=0;
  if (estFeuille(a)) {
    return 0;
  }
  if (a->filsGauche != NULL)
    g = hauteurNN(a->filsGauche);
  if (a->filsDroit != NULL)
    g = hauteurNN(a->filsDroit);
  return 1 + max(g,d);
}

/* Retourne la hauteur de l'arbre. Cette fonction retourne -1 si l'arbre est vide. */
int hauteur(Arbre a) {
  if (a == NULL)
    return -1;
  return hauteurNN(a);
}

/* Affiche les noeuds de l'arbre en ordre préfixe. */
void affichePrefixe(Arbre a) {
  if (a == NULL)
    return;
  printf("%c ", a->info);
  affichePrefixe(a->filsGauche);
  affichePrefixe(a->filsDroit);
}

Arbre enracinerArbre(char c, Arbre fg, Arbre fd) {
  Arbre a = (Arbre) malloc(sizeof(Noeud));
  if (a== NULL) return NULL;
  a->info = c;
  a->filsGauche = fg; 
  a->filsDroit = fd;
  return a;
}


Arbre deTableVersArbreBis(Table *tab, int i) {
  Arbre a;
  if (i>=tab->n) {
    return NULL;
  }
  a = (Arbre) malloc(sizeof(Noeud));
  a->info = tab->t[i];
  a->filsGauche = deTableVersArbreBis(tab,2*i+1);
  a->filsDroit = deTableVersArbreBis(tab,2*i+2);
  return a;
}

Arbre deTableVersArbre(Table *tab) {
  return deTableVersArbreBis(tab,0);
}

int puiss(int a, int b) {
  int p = 1;
  int i;
  for(i = 1; i<=b; i++) {
    p = p*a;
  }
  return p;
}

void rempliTableAvecArbre(Arbre a, Table *tab, int i) {
  tab->t[i] = a->info;
  if (a->filsGauche)
    rempliTableAvecArbre(a->filsGauche, tab, 2*i+1);
  if (a->filsDroit)
    rempliTableAvecArbre(a->filsDroit, tab, 2*i+2);
}

Table *deArbreVersTable(Arbre a) {
  Table *tab;
  tab = (Table *) malloc(sizeof(Table));
  tab->n = puiss(2,hauteur(a)+1)-1;
  tab->t = (char*) malloc(tab->n*sizeof(char));
  rempliTableAvecArbre(a,tab,0);
  return tab; 
}

int main(void) {
  Arbre a;
  int i;
  Table * tab2;
  Table * tab = (Table *) malloc(sizeof(Table));
  tab->t = (char *) malloc(sizeof(char) * 7);
  tab->t[0] = 'A';
  tab->t[1] = 'B';
  tab->t[2] = 'C';
  tab->t[3] = 'D';
  tab->t[4] = 'E';
  tab->t[5] = 'F';
  tab->t[6] = 'G';
  tab->n = 7;
  
  a = deTableVersArbre(tab);
  
  affichePrefixe(a);
  printf("\n");

  tab2 = deArbreVersTable(a);

  for(i=0; i<tab2->n; i++)
    printf("%c ", tab2->t[i]);

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