Cours 5: Le type Arbre binaire.

Voici la signature du type abstrait ArbreB .

// fichier arbre_b.h
#include "noeud_def.h"
#include "element_ab_def.h"
#include "arbre_b_def.h"
ArbreB creer_ab();
Noeud arbre_en_noeud_ab(ArbreB a);
ArbreB noeud_en_arbre_ab(Noeud n);
ArbreB concatener_ab(Noeud n, ArbreB g, ArbreB d);
ArbreB g_ab(ArbreB a);
ArbreB d_ab(ArbreB a);
Element_ab lire_noeud_ab(Noeud n);
Noeud ecrire_noeud_ab(Noeud n, Element_ab e);
Noeud allouer_noeud_ab();
unsigned int est_vide_ab(ArbreB a);
// a1, a2: ArbreB; n: Noeud;
// préconditions
//  g_ab(a1) est-defini-ssi est_vide_ab(a1) == 0
//  d_ab(a1) est-defini-ssi est_vide_ab(a1) == 0
//  lire_noeud_ab(a1) est-defini-ssi est_vide_ab(a1) == 0
//  ecrire_noeud_ab(a1) est-defini-ssi est_vide_ab(a1) == 0
// axiomes
//  est_vide_ab(creer_ab()) != 0
//  arbre_en_noeud_ab(concatener_ab(n, a1, a2)) == n
//  g_ab(concatener_ab(n, a1, a2)) == a1
//  d_ab(concatener_ab(n, a1, a2)) == a2

On peut créer un arbre binaire (creer_ab()), créer un nœud (allouer_nœud_ab()), remplir un nœud d'un élément (ecrire_nœud_ab(Nœud n, Element e)), étendre un arbre binaire en combinant un nœud avec deux arbres (concatener_ab(Nœud n, ArbreB g, ArbreB d)), parcourir un arbre binaire en descendant dans le sous-arbre gauche (g_ab(ArbreB a)) ou dans le sous-arbre droit (d_ab(ArbreB a)), repérer les nœuds d'un arbre binaire (arbre_en_nœud_ab(ArbreB a)) ou repérer le sous-arbre binaire dont la racine est un nœud repéré (nœud_en_arbre_ab(Nœud n)).
Le type Nœud est très utile pour la manipulation des arbres, en particulier leur parcours et leur construction. Ce type abstrait n'est néanmoins pas très utile hors du contexte des arbres binaires. Pour cette raison, le type est intégré à celui des arbres binaires.
On a les fichiers de définition des types abstraits suivants:

// fichier arbre_b_def.h
typedef void * ArbreB;

// fichier noeud_def.h
typedef void * Noeud;

Nous commençons par présenter une implémentation d'arbre binaire en table. La table est représentée par un conteneur pouvant stocker plusieurs arbres, ce qu'on appelle une forêt.
La taille maximale de la forêt est fixée à la constante TAILLE_FORET.
Les éléments de la table sont des nœuds représentés par des triplets (e, g, d) dont la première composante e est le contenu du nœud (l'élément), la seconde composante g est l'accès au sous-arbre gauche (numéro du nœud contenant le fils gauche) et la troisième composante d est l'accès au sous-arbre droit.
Les entrées de la table sont allouées au fur et à mesure de la construction d'un arbre (allocation de nœud). L'entrée à allouer est repérée par la variable interne libre .
On peut allouer un nœud, y écrire un élément et concaténer deux arbres avec un nœud.

// fichier arbre_b_en_table.c
#include <stdio.h>
#include "arbre_b_en_table.h"
// la représentation concrète d'un Noeud est un unsigned int *
// le pointeur pointe sur un entier qui est
// l'index du noeud dans la forêt
// la représentation concrète d'un Arbre est un unsigned int *
// le pointeur pointe sur un entier qui est
// l'index de la racine de l'arbre dans la forêt
// (TAILLE_FORET pour un arbre vide)
typedef struct {Element_ab e; unsigned int g, d;} Nd;
// table de stockage des arbres
Nd foret[TAILLE_FORET];
// premier emplacement libre de la forêt
unsigned int libre;
unsigned int est_vide_ab(ArbreB a) {
 return ((*(unsigned int *)a) == TAILLE_FORET);
}
ArbreB creer_ab() {
 unsigned int *r;
 // un nouvel arbre (vide) a une place en TAILLE_FORET par convention
 r = (unsigned int *) malloc(sizeof(unsigned int));
 *r = TAILLE_FORET;
 return (ArbreB) r;
}
Noeud arbre_en_noeud_ab(ArbreB a) {
 return (Noeud)a;
}
ArbreB noeud_en_arbre_ab(Noeud n) {
 return (ArbreB)n;
}
ArbreB concatener_ab(Noeud n, ArbreB g, ArbreB d){
 unsigned int i;
 i = *((unsigned int *)n);
 foret[i].g = *((unsigned int *)g);
 foret[i].d = *((unsigned int *)d);
 return (ArbreB)n;
}
ArbreB g_ab(ArbreB a){
// précondition: arbre a non vide
 unsigned int i;
 i = *((unsigned int *)a);
 if (i == TAILLE_FORET) {
  fprintf(stderr, "g_ab: arbre vide\n");
  exit(1);
 }
 return (ArbreB) (&foret[i].g);
}
ArbreB d_ab(ArbreB a){
// précondition: arbre a non vide
 unsigned int i;
 i = *((unsigned int *)a);
 if (i == TAILLE_FORET) {
  fprintf(stderr, "d_ab: arbre vide\n");
  exit(1);
 }
 return (ArbreB) (&foret[i].d);
}
Element_ab lire_noeud_ab(Noeud n){
// précondition: noeud existant
 unsigned int i = *((unsigned int *)n);
 if (i >= libre) {
  fprintf(stderr, "lire_noeud_ab: noeud inexistant\n");
  exit(1);
 }
 return (foret[i].e);
}
Noeud ecrire_noeud_ab(Noeud n, Element_ab e){
// précondition: noeud existant
 unsigned int i = *((unsigned int *)n);
 if (i >= libre) {
  fprintf(stderr, "ecrire_noeud_ab: noeud inexistant\n");
  exit(1);
 }
 foret[i].e = e;
 return n;
}
Noeud allouer_noeud_ab(){
// précondition pour les arbres binaires en table: forêt non pleine
 unsigned int *p;
 if (libre == TAILLE_FORET) {
  fprintf(stderr, "allouer_noeud_ab: foret pleine\n");
  exit(1);
 }
 p = (unsigned int *) malloc(sizeof(unsigned int));
 *p = libre;
 foret[*p].g = foret[*p].d = TAILLE_FORET;
 libre++;
 return (Noeud)p;
}

Voici un exemple de mise en œuvre. Le menu permet de construire un arbre: on alloue les nœuds puis on les relie par concaténation. On peut à tout moment vérifier sa construction en faisant un parcours suffixe de l'arbre formé.
Pour construire un arbre binaire incomplet, on utilise un arbre vide qu'on concatène en fils (gauche ou droit).
On ne montre pas pour l'instant de cas de suppression de nœud (on construit et on parcourt).

// fichier main_table.c
#include <stdio.h>
#include "element_int_ab.h"
#include "arbre_b_en_table.h"
#define TAILLE_REP 128
parcours_suffixe(ArbreB a) {
 if (est_vide_ab(a)) return;
 parcours_suffixe(g_ab(a));
 parcours_suffixe(d_ab(a));
 printf("%d ", lire_element_ab(lire_noeud_ab(arbre_en_noeud_ab(a))));
}
main() {
 ArbreB a;
 Element_ab e;
 Noeud table[TAILLE_FORET], n;
 int i, j, k;
 unsigned int nb_noeuds = 1;
 char rep[TAILLE_REP];
 a = creer_ab();
 // noeud vide
 table[0] = arbre_en_noeud_ab(a);
 do {
  afficher_menu();
  fgets(rep, TAILLE_REP, stdin);
  if (rep[0] == 'q') exit(0);
  switch (rep[0]) {
   case 'c':
     sscanf(&rep[1], "%d %d %d", &i, &j, &k);
     if (i >= nb_noeuds) printf("noeud inexistant\n");
     else if (j >= nb_noeuds) printf("noeud inexistant\n");
     else if (k >= nb_noeuds) printf("noeud inexistant\n");
     else concatener_ab(table[k], noeud_en_arbre_ab(table[i]),
          noeud_en_arbre_ab(table[j]));
     break;
   case 'f':
     sscanf(&rep[1], "%d", &i);
     if (nb_noeuds >= TAILLE_FORET) printf("foret pleine\n");
     else {
       n = allouer_noeud_ab();
       e = creer_element_ab();
       e = ecrire_element_ab(e, i);
       n = ecrire_noeud_ab(n, e);
       table[nb_noeuds] = n;
       printf("le noeud alloué est conservé à l'index %d\n", nb_noeuds);
       nb_noeuds++;
     }
     break;
    case 'p':
     sscanf(&rep[1], "%d", &i);
     if (i >= nb_noeuds) printf("noeud inexistant\n");
     else {
      parcours_suffixe(noeud_en_arbre_ab(table[i]));
      printf("\n");
     }
     break;
  }
 } while (1);
}
afficher_menu() {
 printf("menu:\n");
 printf("  (q)uitter\n");
 // retourne un numéro
 printf("  creer une (f)euille de valeur (v)\n");
 printf("  (c)oncatener l'arbre gauche (i), l'arbre droit (j) avec le noeud (k) (arbre vide: 0)\n");
 printf("  (p)arcours de l'arbre de racine (i)\n");
}

On peut construire l'exécutable avec le makefile qui suit.

# fichier make_arbre_b_en_table
main_table: main_table.o arbre_b_en_table.o element_int_ab.o
        cc -o main_table main_table.o arbre_b_en_table.o element_int_ab.o
main_table.o: main_table.c arbre_b.h arbre_b_en_table.h arbre_b_def.h element_ab_def.h element_int_ab.h
        cc -c main_table.c
arbre_b_en_table.o: arbre_b_en_table.c arbre_b.h arbre_b_en_table.h arbre_b_def.h element_ab_def.h
        cc -c arbre_b_en_table.c
element_int_ab.o: element_int_ab.c element_int_ab.h element_ab_def.h
        cc -c element_int_ab.c

Voici une seconde implémentation en liste chaînée.

// fichier arbre_b_en_chaine.c
#include <stdio.h>
#include "arbre_b.h"
typedef struct s {Element_ab e; struct s *g, *d;} Nd;
unsigned int est_vide_ab(ArbreB a) {
 return (a == NULL);
}
ArbreB creer_ab() {
 return (ArbreB) NULL;
}
Noeud arbre_en_noeud_ab(ArbreB a) {
 return (Noeud)a;
}
ArbreB noeud_en_arbre_ab(Noeud n) {
 return (ArbreB)n;
}
ArbreB concatener_ab(Noeud n, ArbreB g, ArbreB d){
 ((Nd *)n)->g = (Nd *)g;
 ((Nd *)n)->d = (Nd *)d;
 return (ArbreB)n;
}
ArbreB g_ab(ArbreB a){
// précondition: arbre a non vide
 if (a == NULL) {
  fprintf(stderr, "g_ab: arbre vide\n");
  exit(1);
 }
 return (ArbreB) (((Nd *)a)->g);
}
ArbreB d_ab(ArbreB a){
// précondition: arbre a non vide
 if (a == NULL) {
  fprintf(stderr, "d_ab: arbre vide\n");
  exit(1);
 }
 return (ArbreB) (((Nd *)a)->d);
}
Element_ab lire_noeud_ab(Noeud n){
// précondition: noeud existant
 if (n == NULL) {
  fprintf(stderr, "lire_noeud_ab: noeud inexistant\n");
  exit(1);
 }
 return (((Nd *)n)->e);
}
Noeud ecrire_noeud_ab(Noeud n, Element_ab e){
// précondition: noeud existant
 if (n == NULL) {
  fprintf(stderr, "ecrire_noeud_ab: noeud inexistant\n");
  exit(1);
 }
 ((Nd *)n)->e = e;
 return n;
}
Noeud allouer_noeud_ab(){
 Nd *n;
 n = (Nd *) malloc(sizeof(Nd));
 n->g = n->d = NULL;
 return (Noeud)n;
}

Le programme de mise en œuvre est presque identique à celui qui précède.

// fichier main_chaine.c
#include <stdio.h>
#include "element_int_ab.h"
#include "arbre_b.h"
#define TAILLE_REP 128
#define TAILLE_FORET 1024
parcours_suffixe(ArbreB a) {
 if (est_vide_ab(a)) return;
 parcours_suffixe(g_ab(a));
 parcours_suffixe(d_ab(a));
 printf("%d ", lire_element_ab(lire_noeud_ab(arbre_en_noeud_ab(a))));
}
main() {
 ArbreB a;
 Element_ab e;
 Noeud table[TAILLE_FORET], n;
 int i, j, k;
 unsigned int nb_noeuds = 1;
 char rep[TAILLE_REP];
 a = creer_ab();
 // noeud vide
 table[0] = arbre_en_noeud_ab(a);
 do {
  afficher_menu();
  fgets(rep, TAILLE_REP, stdin);
  if (rep[0] == 'q') exit(0);
  switch (rep[0]) {
   case 'c':
     sscanf(&rep[1], "%d %d %d", &i, &j, &k);
     if (i >= nb_noeuds) printf("noeud inexistant\n");
     else if (j >= nb_noeuds) printf("noeud inexistant\n");
     else if (k >= nb_noeuds) printf("noeud inexistant\n");
     else concatener_ab(table[k], noeud_en_arbre_ab(table[i]),
          noeud_en_arbre_ab(table[j]));
     break;
   case 'f':
     sscanf(&rep[1], "%d", &i);
     if (nb_noeuds >= TAILLE_FORET) printf("foret pleine\n");
     else {
       n = allouer_noeud_ab();
       e = creer_element_ab();
       e = ecrire_element_ab(e, i);
       n = ecrire_noeud_ab(n, e);
       table[nb_noeuds] = n;
       printf("le noeud alloué est conservé à l'index %d\n", nb_noeuds);
       nb_noeuds++;
     }
     break;
    case 'p':
     sscanf(&rep[1], "%d", &i);
     if (i >= nb_noeuds) printf("noeud inexistant\n");
     else {
      parcours_suffixe(noeud_en_arbre_ab(table[i]));
      printf("\n");
     }
     break;
  }
 } while (1);
}
afficher_menu() {
 printf("menu:\n");
 printf("  (q)uitter\n");
 // retourne un numéro
 printf("  creer une (f)euille de valeur (v)\n");
 printf("  (c)oncatener l'arbre gauche (i), l'arbre droit (j) avec le noeud (k) (arbre vide: 0)\n");
 printf("  (p)arcours de l'arbre de racine (i)\n");
}

Voici le makefile.

# fichier make_arbre_b_en_chaine
main_chaine: main_chaine.o arbre_b_en_chaine.o element_int_ab.o
        cc -o main_chaine main_chaine.o arbre_b_en_chaine.o element_int_ab.o
main_chaine.o: main_chaine.c arbre_b.h arbre_b_def.h element_ab_def.h element_int_ab.h
        cc -c main_chaine.c
arbre_b_en_chaine.o: arbre_b_en_chaine.c arbre_b.h arbre_b_def.h element_ab_def.h
        cc -c arbre_b_en_chaine.c
element_int_ab.o: element_int_ab.c element_int_ab.h element_ab_def.h
        cc -c element_int_ab.c

Voici maintenant un algorithme de parcours d'arbre en largeur d'abord. On visite successivement tous les nœuds d'un niveau de l'arborescence avant de descendre au niveau inférieur. L'algorithme emploie une file dans laquelle on ajoute les deux fils du nœud courant. On visite les nœuds dans l'ordre de la file.

// fichier parcours_largeur.c
#include <stdio.h>
// pour les éléments (int) conservés dans les noeuds de l'arbre
#include "element_ab.h"
#include "arbre_b_en_table.h"
// pour les éléments conservés dans la file (ArbreB)
#include "element_ab_file.h"
#include "file.h"
File f;
ArbreB construire_arbre();
parcours_suffixe_iteratif(ArbreB a) {
 Element_file e;
 ArbreB b;
 if (est_vide_ab(a)) return;
 b = creer_ab();
 f = creer_file();
 e = creer_element_file(f);
 e = ecrire_element_file(e, a);
 b = lire_element_file(f);
 f = ajouter_file(f, e);
 b = tete_file(f);
 do {
   a = tete_file(f);
   f = retirer_file(f);
   if (est_vide_ab(a)) continue;
   printf("%d\n", lire_element_ab(lire_noeud_ab(arbre_en_noeud_ab(a))));
   e = creer_element_file(f);
   e = ecrire_element_file(e, g_ab(a));
   f = ajouter_file(f, e);
   e = creer_element_file(f);
   e = ecrire_element_file(e, d_ab(a));
   f = ajouter_file(f, e);
 } while (!est_vide_file(f));
}
main() {
 ArbreB a;
 a = creer_ab();
 a = construire_arbre();
 parcours_suffixe_iteratif(a);
}
ArbreB construire_arbre(){
 Element_ab e;
 Noeud table[32], n;
 ArbreB b;
 b = creer_ab();
 table[31] = arbre_en_noeud_ab(b);
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 0);
 n = ecrire_noeud_ab(n, e);
 table[0] = n;
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 1);
 n = ecrire_noeud_ab(n, e);
 table[1] = n;
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 2);
 n = ecrire_noeud_ab(n, e);
 table[2] = n;
 concatener_ab(table[0], noeud_en_arbre_ab(table[1]),
               noeud_en_arbre_ab(table[2]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 3);
 n = ecrire_noeud_ab(n, e);
 table[3] = n;
 concatener_ab(table[1], noeud_en_arbre_ab(table[3]),
               noeud_en_arbre_ab(table[31]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 4);
 n = ecrire_noeud_ab(n, e);
 table[4] = n;
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 5);
 n = ecrire_noeud_ab(n, e);
 table[5] = n;
 concatener_ab(table[2], noeud_en_arbre_ab(table[4]),
               noeud_en_arbre_ab(table[5]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 6);
 n = ecrire_noeud_ab(n, e);
 table[6] = n;
 concatener_ab(table[3], noeud_en_arbre_ab(table[31]),
               noeud_en_arbre_ab(table[6]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 7);
 n = ecrire_noeud_ab(n, e);
 table[7] = n;
 concatener_ab(table[4], noeud_en_arbre_ab(table[31]),
               noeud_en_arbre_ab(table[7]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 8);
 n = ecrire_noeud_ab(n, e);
 table[8] = n;
 concatener_ab(table[5], noeud_en_arbre_ab(table[8]),
               noeud_en_arbre_ab(table[31]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 9);
 n = ecrire_noeud_ab(n, e);
 table[9] = n;
 concatener_ab(table[6], noeud_en_arbre_ab(table[31]),
               noeud_en_arbre_ab(table[9]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 10);
 n = ecrire_noeud_ab(n, e);
 table[10] = n;
 concatener_ab(table[8], noeud_en_arbre_ab(table[31]),
               noeud_en_arbre_ab(table[10]));
 return (noeud_en_arbre_ab(table[0]));
}

Voici le fichier element_ab_file.h

// fichier element_ab_file.h
#include "element_file_def.h"
#include "arbre_b_def.h"
Element_file creer_element_file();
Element_file ecrire_element_file(Element_file e, ArbreB a);
ArbreB lire_element_file(Element_file e);

Voici le fichier element_ab_file.c

// fichier element_ab_file.c
#include "element_ab_file.h"
Element_file creer_element_file() {
 ArbreB p;
 p = (ArbreB) malloc(sizeof(ArbreB));
 return (Element_file) p;
}
Element_file ecrire_element_file(Element_file e, ArbreB a) {
 e = a;
 return e;
}
ArbreB lire_element_file(Element_file e) {
 return (ArbreB)e;
}

Pour l'arbre ci-dessous, le parcours en largeur liste les entiers dans l'ordre.

Voici maintenant un parcours en profondeur en version itérative. On empile, à chaque nœud visité, le nœud père ainsi qu'un indicateur précisant si le nœud courant en est le fils gauche (sens == 0) ou le fils droit (sens == 1). Lorsqu'on a atteint une feuille, on remonte au père en dépilant, le sens dépilé nous indiquant si l'on doit continuer à remonter (sens == 1) ou descendre vers le fils droit (sens == 0).

// fichier parcours_profondeur.c
#include <stdio.h>
#include "element_ab.h"
#include "arbre_b_en_table.h"
#include "element_pile.h"
#include "pile.h"
Pile p;
ArbreB construire_arbre();
parcours_suffixe_recursif(ArbreB a) {
 if (est_vide_ab(a)) return;
 parcours_suffixe_recursif(g_ab(a));
 parcours_suffixe_recursif(d_ab(a));
 printf("%d\n", lire_element_ab(lire_noeud_ab(arbre_en_noeud_ab(a))));
}
parcours_suffixe_iteratif(ArbreB a) {
 // sens == 0 ssi on remonte par la gauche
 // sens == 1 ssi on remonte par la droite
 unsigned int sens = 0;
 Element_pile e;
 p = creer_pile();
 do {
  if (sens == 0) {
   while (!est_vide_ab(a)) {
    e = creer_element_pile();
    e = ecrire_element_pile(e, a, 0);
    p = empiler_pile(p, e);
    a = g_ab(a);
   }
  }
  if (!est_vide_pile(p)) {
   e = sommet_pile(p);
   a = lire_arbre_element_pile(e);
   sens = lire_sens_element_pile(e);
   p = depiler_pile(p);
   if (sens == 0) {
    e = creer_element_pile();
    e = ecrire_element_pile(e, a, 1);
    p = empiler_pile(p, e);
    a = d_ab(a);
   }
   else printf("%d\n", lire_element_ab(lire_noeud_ab(arbre_en_noeud_ab(a))));
  }
 } while (!est_vide_pile(p));
}
main() {
 ArbreB a;
 a = creer_ab();
 a = construire_arbre();
 parcours_suffixe_recursif(a);
 parcours_suffixe_iteratif(a);
}
ArbreB construire_arbre(){
 Element_ab e;
 Noeud table[32], n;
 ArbreB b;
 b = creer_ab();
 table[31] = arbre_en_noeud_ab(b);
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 0);
 n = ecrire_noeud_ab(n, e);
 table[0] = n;
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 1);
 n = ecrire_noeud_ab(n, e);
 table[1] = n;
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 2);
 n = ecrire_noeud_ab(n, e);
 table[2] = n;
 concatener_ab(table[0], noeud_en_arbre_ab(table[1]),
               noeud_en_arbre_ab(table[2]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 3);
 n = ecrire_noeud_ab(n, e);
 table[3] = n;
 concatener_ab(table[1], noeud_en_arbre_ab(table[3]),
               noeud_en_arbre_ab(table[31]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 4);
 n = ecrire_noeud_ab(n, e);
 table[4] = n;
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 5);
 n = ecrire_noeud_ab(n, e);
 table[5] = n;
 concatener_ab(table[2], noeud_en_arbre_ab(table[4]),
               noeud_en_arbre_ab(table[5]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 6);
 n = ecrire_noeud_ab(n, e);
 table[6] = n;
 concatener_ab(table[3], noeud_en_arbre_ab(table[31]),
               noeud_en_arbre_ab(table[6]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 7);
 n = ecrire_noeud_ab(n, e);
 table[7] = n;
 concatener_ab(table[4], noeud_en_arbre_ab(table[31]),
               noeud_en_arbre_ab(table[7]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 8);
 n = ecrire_noeud_ab(n, e);
 table[8] = n;
 concatener_ab(table[5], noeud_en_arbre_ab(table[8]),
               noeud_en_arbre_ab(table[31]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 9);
 n = ecrire_noeud_ab(n, e);
 table[9] = n;
 concatener_ab(table[6], noeud_en_arbre_ab(table[31]),
               noeud_en_arbre_ab(table[9]));
 e = creer_element_ab();
 n = allouer_noeud_ab();
 e = ecrire_element_ab(e, 10);
 n = ecrire_noeud_ab(n, e);
 table[10] = n;
 concatener_ab(table[8], noeud_en_arbre_ab(table[31]),
               noeud_en_arbre_ab(table[10]));
 return (noeud_en_arbre_ab(table[0]));
}

L'arbre construit est le même que pour le parcours en largeur. Le traitement suffixe des nœuds les liste dans l'ordre 9, 6, 3, 1, 7, 4, 10, 8, 5, 2, 0.

Voici le fichier element_pile.h qui décrit les éléments empilés. Ce sont des couples (ArbreB, int) (nœud père et sens).

// fichier element_pile.h
#include "element_pile_def.h"
#include "arbre_b_def.h"
Element_pile creer_element_pile();
Element_pile ecrire_element_pile(Element_pile e, ArbreB a, unsigned int sens);
ArbreB lire_arbre_element_pile(Element_pile e);
unsigned int lire_sens_element_pile(Element_pile e);

Voici le fichier element_pile.c

// fichier element_pile.c
#include "element_pile.h"
typedef struct {ArbreB a; unsigned int sens;} Couple;
Element_pile creer_element_pile() {
 Couple *p;
 p = (Couple *) malloc(sizeof(Couple));
 return (Element_pile) p;
}
Element_pile ecrire_element_pile(Element_pile e, ArbreB a, unsigned int sens) {
 ((Couple *)e)->a = a;
 ((Couple *)e)->sens = sens;
 return e;
}
ArbreB lire_arbre_element_pile(Element_pile e) {
 return ((Couple *)e)->a;
}
unsigned int lire_sens_element_pile(Element_pile e) {
 return ((Couple *)e)->sens;
}