LES ARBRES EN C - TREES PROGRAMMED IN C

Types d'arbres
Les arbres sont divisés en deux catégories, les arbres binaires et les arbres n-aires.

Arbre binaire
Ce sont des arbres au plus de degré 2, c'est-à-dire dans lesquels chaque noeud a au plus
deux fils. Les fils sont en général nommés fils gauche et fils droit. C'est un arbre
ordonné, c'est-à-dire que les fils gauche et droite ne sont pas interchangeables.
Les arbres binaires sont majoritairement utilisés dans les algorithmes.

Arbre n-aire
C'est un arbre dans lequel au moins un noeud possède plus de deux fils, c'est-à-dire un
arbre de degré supérieur à 2. Ces arbres sont en général peu utilisés dans les algorithmes
parce qu'ils peuvent toujours être convertis en arbres binaires qui sont plus simples à
manipuler.

Nous allons créer un arbre dynamique. Nous avons besoin d'un tableau de caractères
pour stocker une chaîne (ou éventuellement juste un caractère puisqu'il n'y a que des
caractères à stocker) et de deux pointeurs, un pour le fils gauche et un pour le fils droit.
La structure de données est la suivante :

#define DATMAX 80
typedef struct noeud{
  char dat[DATMAX];
  struct noeud*g, *d;
}t_noeud;

Voici une fonction pour initialiser un noeud de l'arbre :
t_noeud* CN(char s[], t_noeud*g, t_noeud*d)
{
t_noeud*n;
  n=(t_noeud*)malloc(sizeof(t_noeud));
  strcpy_s(n->s, DATMAX, s);
  n->g=g;
  n->d=d;
  return n;
}

et la fonction pour créer l'arbre :
t_noeud* creerArbre()
{
  return CN("A",
    CN("B",
      CN("D", NULL, NULL),
      CN("E", NULL, NULL),
    CN("C",
      CN("F",
        CN("H", NULL, NULL),
        NULL),
        CN("G",NULL, NULL)
    );
}

Créer un arbre en insérant des éléments ordonnés
L'objectif est ici de créer un arbre en ajoutant au fur et à mesure des nouveaux noeuds
dans l'arbre. Les nouveaux noeuds sont toujours ajoutés au niveau des feuilles (les
noeuds suivis par aucun noeud), pas entre les noeuds internes. Ils sont répartis selon
les valeurs alphabétiques. L'algorithme est le suivant : si la valeur lexicographique de
la lettre du nouveau noeud est avant celle du noeud courant; partir à gauche, sinon
partir à droite et en partant de la racine jusqu'à arriver à une feuille. Pour pouvoir
accrocher le nouveau noeud, il est nécessaire de conserver pendant la descente l'adresse
du noeud précédent afin d'avoir l'adresse de la feuille finale à laquelle accrocher le
nouveau noeud qui devient une nouvelle feuille : 

void inserer(t_noeud**racine, t_noeud*n)
{
t_noeud*x,*prec;
  // si pas de racine il devient racine
  if(*racine==NULL)
    *racine=n;
  // sinon descendre jusqu'à une feuille (fils g et d à NULL)
  else {
    x=*racine; // pour descendre
    prec=NULL; // pour conserver position précédente
    while(x!=NULL){
      prec=x; // save position précédente
      x=(strcmp(n->dat,x->dat)<0)?x->g:x->d; // descente selon n
    }
    // à l'issue accrocher
    if (strcmp(n->dat,prec->dat)<0)
      prec->g=n;
    else
      prec->d=n;
  }
}

Parcours en profondeur préfixé :

Algorithme récursif :
void prefixe(t_noeud*r)
{
  if(r!=NULL){
    printf("%s",r->dat);
    prefixe(r->g);
    prefixe(r->d);
  }
}

Algorithme itératif, gestion pile :
prefixe_iter(t_noeud*r)
{
  empiler(r);
  while(!pile_vide()){
    r=depiler();
    visiter(r);
    // attention inversion
    // droite d'abord
    // puis gauche
    if(r->d) empiler(r->d);
    if(r->g) empiler(r->g);
  }
}