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


char *profs[] = {
  "Francois", "Bruno", "Patrice", "Jean",   "Francois", "Robert",
  "Francois", "Jean",   "Francois", "Didier",  "Didier", "Bruno",
  "Jean", "Francois", "Jean"
};


typedef struct cell {
  char *mot;
  int compte;
  struct cell *filsg,*filsd;
} Cell, *Tree;

Tree cons(char *mot,int compte,Tree filsg,Tree filsd)
{
  Tree r;

  r = (Tree )malloc(sizeof(struct cell));
  if ( r == NULL) {
    fprintf(stderr,"Plus de memoire\n");
    exit(-1);
  }
  r->mot = mot;
  r->compte = compte;
  r->filsg = filsg;
  r->filsd = filsd;
  return r;
}

void affiche(Tree t)
{
  if (t != NULL) {
    affiche(t->filsg);
    printf("%s : %d\n",t->mot,t->compte);
    affiche(t->filsd);
  }
}

Tree add(char *mot,Tree t)
{
  int cond;

  if (t == NULL)
    return cons(mot,1,NULL,NULL);

  cond = strcmp(mot,t->mot);
  if (cond < 0)
    t->filsg = add(mot,t->filsg);
  else if (cond > 0)
    t->filsd = add(mot,t->filsd);
  else
    t->compte++;
  return t;
}

Tree insert(int compte,char *mot,Tree t)
{

  if (t == NULL)
    return cons(mot,compte,NULL,NULL);

  if (compte > t->compte)
    t->filsg = insert(compte,mot,t->filsg);
  else  /* astuce, on a toujours mot > t->mot */
    t->filsd = insert(compte,mot,t->filsd);

  return t;
}

/*
  Produit un nouvel arbre ordonne selon les comptes,
  Le parcours doit etre infixe pour garantir que les prenoms nouvellement
  inseres dans le second arbre sont plus grands que ceux qui s'y trouvent
  deja

  Cette facon de proceder produira plus facilement un arbre desequilibre.

  Pour produire un arbre mieux equilibre, il vaut sans doute mieux
  qu'ordonne parcours l'arbre de facon prefixe et que insert teste
  les prenoms :

  Tree insert(int compte,char *mot,Tree t)
  {
    int cond;
  
    if (t == NULL)
      return cons(mot,compte,NULL,NULL);
  
    if (compte < t->compte)
      cond = -1;
    else if (compte > t->compte)
      cond = 1;
    else
      cond = -strcmp(mot,t->mot);
  
    if (cond > 0)
      t->filsg = insert(compte,mot,t->filsg);
    else
      t->filsd = insert(compte,mot,t->filsd);
    return t;
  }
  
  Tree ordonne(Tree t,Tree r)
  {
    if (t == NULL)
      return r;
    r = insert(t->compte,t->mot,r);
    r = ordonne(t->filsg,r);
    r = ordonne(t->filsd,r);
    return r;
  }

  Neamoins, dans la pratique, les deux arbres sont tres desequilibre's.

*/

Tree ordonne(Tree t,Tree r)
{
  if (t == NULL)
    return r;
  r = ordonne(t->filsg,r);
  r = insert(t->compte,t->mot,r);
  r = ordonne(t->filsd,r);
  return r;
}

void main(void)
{
  Tree tous_mots = NULL;
  int i;

  for (i=0 ; i < sizeof(profs)/sizeof(profs[0])-1 ; i++)
    tous_mots = add(profs[i],tous_mots);

  affiche(tous_mots);
  printf("\n\n");
  affiche(ordonne(tous_mots,NULL));
}