//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Structure de données

struct cell {
  char mot[22] ;
  struct cell *fg ; 
  struct cell *fd ; 
} ;

typedef struct cell cellule ;

cellule * racine ;

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Utilitaires d'affichage et de sortie de l'ABR
// le paramètre entier correspond à une indentation (pretty print)

void aff_tree (cellule * r, int p)
{
  int i ;
  if (r != NULL) {
    aff_tree(r->fg, p+3) ;
    for (i=0 ; i<p ; i++) printf("%c", ' ') ;
    printf("%s\n", r->mot) ;
    aff_tree(r->fd, p+3) ;
  }
}


//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Calculs sur la structure : nombre de noeuds, profondeur

int nb_mots (cellule * r)
{
  if (r == NULL) return 0 ;
  return 1 + nb_mots(r->fg) + nb_mots(r->fd) ;
}

int max(int a, int b) {   return a>b?a:b ; }

int profondeur (cellule * r)
{
  if (r == NULL) return 0 ;
  return max(profondeur(r->fg),profondeur(r->fd)) + 1 ;
}
  
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Primitives de création et de manipulation de l'ABR

cellule * cree_cell(char * mot)
{
  cellule * x = (cellule *) malloc(sizeof(cellule)) ;
  if (x == NULL) { fprintf(stderr, "Erreur d'allocation\n") ; exit(1) ;}
  strcpy(x->mot, mot) ;
  x->fg = x->fd = NULL ;
  return x ;
}