#include<stdio.h>
#include<stdlib.h>
/* Un arbre binaire est défini récursivement comme 
- ou bien une feuille, appelée aussi arbre vide,
- ou bien un noeud qui contient une clé et
   deux (sous-)arbres, appelés fils droit et fils gauche.
En C en fait un arbre sera un pointeur sur un noeud, et l'arbre vide sera représenté
par une valeur spéciale de pointeur, comme le pointeur nul. */
typedef int elem;
typedef struct noeud noeud, *abr;
struct noeud { elem clef; abr fg,fd; };
/* La taille d'un arbre binaire est le nombre de ses feuilles.
C'est donc un de plus que le nombre de ses noeuds.
La taille est toujours un entier naturel strictement positif.
La taille d'un arbre représenté par un noeud est la somme des tailles de ses deux fils.
La hauteur d'un arbre binaire est la longueur de sa plus longue branche.
On peut calculer la taille et la hauteur avec les fonctions suivantes : */
int taille(abr a) { return a ? taille(a->fg)+taille(a->fd) : 1 ; }
int maxi(int a,int b) { return a>b?a:b;}
int hauteur(abr a) { return a ? 1+maxi(hauteur(a->fg),hauteur(a->fd)) : 0 ; }
/* Un arbre binaire est dit «de recherche» si la clé d'un noeud quelconque est toujours
strictement plus grande que toutes les clés de son sous-arbre gauche et strictement plus
petite que toutes les clés de son sous-arbre droit.
Autrement dit les clés de l'arbre doivent être affichées dans l'ordre croissant par
la procédure récursive suivante : */
#define recursif 1
#if recursif
void aff(abr a) { if(a) aff(a->fg), printf(" %d",a->clef), aff(a->fd); }
/* Dans cette procédure, on peut remplacer le dernier appel récursif par une itération : */
#else
void aff(abr a) { for(;a;a=a->fd) aff(a->fg), printf(" %d",a->clef); }
#endif
void affln(abr a) {aff(a),printf("\n");}
/* recherche du noeud contenant une clé donnée */
#if recursif
abr recherche(abr a,elem x)
{ return !a         ? a :
         x==a->clef ? a :
         x> a->clef ? recherche(a->fd,x) :
                      recherche(a->fg,x) ;
}
#else
abr recherche(abr a,elem x)
{ while(a && x!=a->clef) a=x>a->clef ? a->fd : a->fg;
  return a;
}
#endif

/* TD 
compléter les procédures et fonctions suivantes : */
abr nn(abr fg,elem clef,abr fd) // nouveau noeud
{ }
abr n2(elem x) { return nn(0,x,0); }
abr copie(abr a)
{ }
abr eipoc(abr a) // crée un arbre contenant des clés de signe opposé
{ }
void test(abr b,abr a)
{ if(b && b->clef>=a->clef) printf("raté %d<%d\n",b->clef,a->clef), exit(1); }
void verif(abr a)
{ abr b=0;
  void ver(abr a)
  { for(;a;a=a->fd)
     test(a->fg,a), // Cette ligne est-elle vraiment utile ?
     ver(a->fg),
     test(b,a), b=a;
  }
  ver(a);
}
void affarbre(abr r)
{ void af(abr a)
  { for(;a;a=a->fg)
    { int dd,d=2;
      abr p=a->fg;
      a->fg=0, af(a->fd), a->fg=p;
      for(p=r;p!=a;p=d?p->fd:p->fg) dd=d,d=!p->fg,printf(dd-!d?"   ":"|  ");
      printf("%c--+  %d\n","\\/-"[d],a->clef);
    }
  }
  af(r);
}
void Aff(abr a) {affln(a),affarbre(a);}
void libere(abr a) 
{ }
abr rotg(abr a)
{ abr b=a->fd;
  a->fd=b->fg, b->fg=a;
  return b;
}
abr linearise(abr a)
{ }
abr equilibre(abr a)
{ }
abr insere(abr a,elem x)
{ }
elem pluspetit(abr a) { }
abr enleve(abr a,elem x)
{ }
int main()
{ int i;
  abr a=nn(n2(1),2,n2(3)), b=copie(a), c=eipoc(a);
  Aff(a);
  Aff(b);
  Aff(c);
  for(i=0;i<10;i++) a=insere(a,i*3%10*2), Aff(a), verif(a);
  Aff(a);
  a=linearise(a);
  Aff(a);
  for(i=0;i<30;i+=3) printf("%d %s\n",i,recherche(a,i)?"oui":"non");
  for(i=0;i<10;i++) a=enleve(a,i*3%10*2), verif(a), Aff(a);
  return 0;
}