/* définitions :
Un arbre est un graphe connexe sans cycle.
Une forêt est un ensemble d'arbres.
Autrement dit une forêt est un graphe sans cycle.

théorème :
Entre deux sommets d'un arbre il y a un chemin et un seul.

Arbre avec racine :
A partir d'un sommet S quelconque d'un arbre il existe un
chemin unique menant de ce sommet à la racine.
Le premier sommet P rencontré sur ce chemin est le père de S.
S est un fils de P.

On peut représenter les arbres en donnant pour chaque sommet
la liste de ses fils.
Puisque chaque sommet n'a qu'un père, il est dans une seule liste
de fils; On peut donc utiliser les sommets eux-mêmes comme
chainons des listes chaînées. */

#include<stdio.h>
#include<stdlib.h>
typedef struct node node, *arbre;
struct node{ arbre fils,frere;
             char *nom;
             int val;
           };
/* Ecrire une procédure qui affiche les noms de tous les sommets
d'un arbre : */
void aff1(arbre a)
{ arbre j;
  printf("%s ",a->nom);
  for(j=a->fils;j;j=j->frere) aff1(j);
}
void aff2(arbre a)
{ if(a)
  { printf("%s ",a->nom);
    aff2(a->fils);
    aff2(a->frere);
  }
}
/* aff1(A) et aff2(A) affichent la même chose si A n'est pas vide et
n'a pas de frère.

En s'inspirant des deux procédures précédentes écrire une fonction
qui calcule la somme des valeurs des noeuds d'un arbre. */
int somval1(arbre a)
{ arbre j;
  int s=a->val;
  for(j=a->fils;j;j=j->frere) s+=somval1(j);
  return s;
}
int somval2(arbre a)
{ if(a) return a->val+somval2(a->fils)+somval2(a->frere);
  else  return 0;
}
int somval3(arbre a)
{ return a ? a->val+somval3(a->fils)+somval3(a->frere) : 0;
}
/* definition (récursive) :
Un arbre binaire est ou bien un arbre vide ou bien un noeud
qui a deux fils qui sont des arbres binaires : un fils droit
et un fils gauche, (qui peuvent chacun être vides ou non).
Si un noeud n'a qu'un fils, ce fils peut être son fils droit
ou son fils gauche. Ce n'est pas la même chose.

Un arbre binaire de recherche est un arbre binaire tel que pour
chacun de ses sous-arbres la valeur du noeud est (strictement)
plus grande que la valeur de chacun des noeuds du sous-arbre gauche
et (strictement) plus petite que la valeur de chacun des noeuds du
sous-arbre droit. */
typedef struct noeud noeud, *arbin;
struct noeud{ arbin fg,fd;
              int val;
            };
/* Ecrire une procédure qui affiche dans l'ordre croissant
les valeurs rangées dans un arbre binaire de recherche. */

void aff(arbin a)
{ if(a) aff(a->fg), printf("%d ",a->val), aff(a->fd); }

/* Ecrire une fonction qui calcule la somme des valeurs rangées
dans un arbre binaire. */

int somval(arbin a)
{ return a ? a->val+somval(a->fg)+somval(a->fd) : 0; }

/* Ecrire une fonction booléenne qui indique si un nombre donné est
dans un arbre binaire de recherche. */

int present1(int x, arbin a)
{ if(a) if(x==a->val) return 1; else
        if(x< a->val) return present1(x,a->fg);
        else          return present1(x,a->fd);
  else                return 0;
}
int present2(int x, arbin a)
{ return a ? x==a->val ? 1
                       : present2(x, x<a->val ? a->fg : a->fd)
           : 0;
}
arbin present3(int x, arbin a)
{ while(a && x!=a->val) a=x<a->val ? a->fg : a->fd;
  return a;
}

/* Ecrire une procédure qui ajoute un élément dans un arbre binaire
de recherche : */
void ajoute1(int x,arbin *aa)
{ arbin a=*aa;
  if(a) if(x==a->val) ; else
        if(x< a->val) ajoute1(x,&a->fg);
        else          ajoute1(x,&a->fd);
  else
  { *aa=a=malloc(sizeof(*a));
    a->val=x;
    a->fg=a->fd=0;
  }
}
void ajoute2(int x,arbin *aa)
{ arbin a;
  while(a=*aa,a) if(x==a->val) return;
                 else aa=x<a->val ? &a->fg : &a->fd;
  *aa=a=malloc(sizeof(*a));
  a->val=x;
  a->fg=a->fd=0;
}
/* Ecrire une procédure qui affiche l'arbre
        5
      /   \
    2       7
   / \
  0   4
     /
    3
sous la forme
  7
5
    4
      3
  2
    0     */
void affarb1(int marge,arbin a)
{ if(a)
   affarb1(marge+2,a->fd),
   printf("%*s%d\n",marge,"",a->val),
   affarb1(marge+2,a->fg);
}
void affarbin1(arbin a){printf("\n"), affarb1(0,a);}
/* sous la forme
  /-7
--5
    /-4
      \-3
  \-2
    \-0  */
void affarb2(int marge,char slash,arbin a)
{ if(a)
   affarb2(marge+2,'/',a->fd),
   printf("%*c-%d\n",marge+1,slash,a->val),
   affarb2(marge+2,'\\',a->fg);
}
void affarbin2(arbin a){printf("\n"), affarb2(0,'-',a);}
/* sous la forme
    /-+7
 --+5
   |   /-+4
   |  |   \-+3
    \-+2
       \-+0  */
void affarb3(arbin r,arbin a)
{ for(;a;a=a->fg)
  { int d, dd=2;
    arbin x=a->fg;
    a->fg=0, affarb3(r,a->fd), a->fg=x;
    for(x=r;x!=a;x=d ? x->fd : x->fg)
     d=!x->fg, printf(d==dd ? "|  " : "   "), dd=!d;
    printf(" %c-+%d\n","/\\-"[dd],a->val);
  }
}
void affarbin3(arbin a){printf("\n"), affarb3(a,a);}

void verif(arbin a,arbin *xx)
{ for(;a;a=a->fd)
  { verif(a->fg,xx);
    if(*xx && (*xx)->val>=a->val)
     printf("\n%d>=%d\n",(*xx)->val,a->val), exit(1);
    *xx=a;
  }
}
void verifarbin(arbin a) {arbin x=0; verif(a,&x);}

arbin detache(int x,arbin *aa)
{ arbin a,b,*bb;
  while(a=*aa,a && a->val!=x) aa=x<a->val ? &a->fg : &a->fd;
  if(!a    ) return 0;
  if(!a->fg) return *aa=a->fd, a;
  if(!a->fd) return *aa=a->fg, a;
  for(bb=&a->fd;b=*bb,b->fg;bb=&b->fg);
  *bb=b->fd;
  b->fg=a->fg;
  b->fd=a->fd;
  *aa=b;
  return a;
}
/* Faire tourner le programme */
void affverif(arbin a)
{ aff(a), printf("%10d",somval(a));
  affarbin1(a), affarbin2(a), affarbin3(a), verifarbin(a);
}
int main()
{ int i;
  arbin a=0,b;
  for(i=10;i--;)   ajoute2(i*i%23,&a), affverif(a);
  for(i=10;i--;) b=detache(i*i%23,&a), affverif(a), free(b);
  return 0;
}