#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;
}

/* L'astuce consiste a inserer un noeud complet, plutot que son contenu */

Tree insert(Tree node,Tree t)
{
  int cond;

  if (t == NULL)
    return node;

  if (node->compte < t->compte)
    cond = -1;
  else if (node->compte > t->compte)
    cond = 1;
  else
    cond = -strcmp(node->mot,t->mot);

  if (cond > 0)
    t->filsg = insert(node,t->filsg);
  else
    t->filsd = insert(node,t->filsd);
  return t;
}

Tree ordonne(Tree t,Tree r)
{
  Tree filsg,filsd;

  if (t == NULL)
    return r;

  filsg = t->filsg;
  filsd = t->filsd;
  t->filsg = NULL;
  t->filsd = NULL;

  r = insert(t,r); /* inserer la feuille t dans l'arbre r */
  r = ordonne(filsg,r);
  r = ordonne(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));
}