/* Un programme pour construire un arbre binaire de recherche
a partir d'un tableau trie */

#include <stdio.h>

#define N 25

int tableau[N];

struct noeud {
  struct noeud *gauche;
  struct noeud *droit;
  int cle; 
};

creer_tableau(){
  int i;

  for(i=0;i<N;i++){
    tableau[i]=i;
  }
}

creer_arbre(int debut, int fin, struct noeud *source){
  int milieu;

  milieu=(debut+fin)/2;
  source->cle=tableau[milieu];
  if (debut<milieu) {
    source->gauche=(struct noeud *) malloc(sizeof(struct noeud));
    creer_arbre(debut,milieu-1,source->gauche);
  }
  else source->gauche=NULL; /*On est oblige de traiter ce cas ici pour pouvoir mettre la valeur*/
  if (milieu<fin) {         /*du pointeur a NULL */
    source->droit=(struct noeud *) malloc(sizeof(*source));
    creer_arbre(milieu+1,fin,source->droit);
  }
  else source->droit=NULL;
}

main(){
  struct noeud racine;
  struct noeud *parcours;
  char d[6]="droit";
  char g[6]="gauche";
  char *s;
   
  creer_tableau();
  creer_arbre(0,N-1,&racine);
  s=d;
  parcours=&racine;
  while(parcours!=NULL){   /* cette boucle est stupide : elle affiche une branche de l'arbre ce qui permet de verifier qu'on ne s'est pas trop trompe */
    printf("Ma cle est %d et je passe a mon fils %s\n",parcours->cle,s); 
    if (s[0]=='d') {
      s=g;
      parcours=parcours->droit;
    } 
    else {
      s=d;
      parcours=parcours->gauche;
    }
  }
}