/* Programme de test pour le corrigé de l'exercice 4 DST n°1 LI032 01/02 */

/*   Rappel de l'énoncé :
   On suppose que l'on dispose d'un Arbre Binaire de Recherche dont
   chaque noeud est un entier, et qui est codé dans un tableau
   d'entiers, de telle sorte que pour tout sommet, s'il se trouve à la
   case i du tableau, son fils gauche se trouve à la case 2xi, et son
   fils droit à la case 2xi+1. 
   Proposer un algorithme qui, étant donné un tel tableau et un entier
   X, détermine l'appartenance de X à l'ABR, de façon optimale
   (c'est-à-dire sans parcourir la totalité du tableau !).
*/

/* Tableau donné en exemple */
/* Attention, on commence à la case 1 ! (sinon 2*i = i) */
int m[33] = {-1,7,4,10,1,6,8,0,0,0,0,0,0,9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ;


int appartient(int x, int i) 
{
  if (m[i] == 0) return 0 ;
  if (m[i] == x) return 1 ;
  if (m[i] > x) return appartient(x, 2*i) ;
  else return appartient(x, 2*i+1) ;
}


/* Programme principal de test.
   Il contient une boucle « infinie » qu'il faut interrompre par
   Ctrl-C */
main()
{
  int val ;

  while (1) {
    printf("Valeur ? ") ;
    scanf("%d", &val) ;
    if (appartient(val,1)) printf("OUI !\n") ;
    else printf("NON !\n") ;
  }
  
}