Le même arbre en C

Le type, et ce qui remplace le filtrage.

typedef struct noeud_s {
    int etiquette;
    struct noeud_s* gauche;    /* NULL joue le role de Vide */
    struct noeud_s* droit;
} noeud;

C n'a pas de types somme : le constructeur Vide est représenté par NULL, et le filtrage par un if (a == NULL). Cette traduction n'est pas gratuite : rien n'oblige le programmeur à traiter le cas NULL, là où le compilateur OCaml refuse un match non exhaustif. La première ligne de chaque fonction est donc un test, et l'oublier produit une violation de segment.

/* Nombre de noeuds de a. NULL designe l'arbre vide.
   Precondition  : a est un arbre bien forme (aucun cycle).
   Complexite    : Theta(n) en temps, O(h) en pile. */
int taille(const noeud* a) {
    if (a == NULL) { return 0; }
    return 1 + taille(a->gauche) + taille(a->droit);
}

/* Hauteur de a ; celle de l'arbre vide vaut -1.
   Postcondition : hauteur(a) >= -1, et vaut -1 exactement si a == NULL. */
int hauteur(const noeud* a) {
    if (a == NULL) { return -1; }
    int hg = hauteur(a->gauche);
    int hd = hauteur(a->droit);
    return 1 + (hg > hd ? hg : hd);
}

/* Nombre de feuilles : les noeuds dont LES DEUX fils sont vides. */
int feuilles(const noeud* a) {
    if (a == NULL) { return 0; }
    if (a->gauche == NULL && a->droit == NULL) { return 1; }
    return feuilles(a->gauche) + feuilles(a->droit);
}

Trois points d'écriture qui comptent.

Le const : les trois fonctions promettent de ne rien modifier, et le compilateur le vérifie. C'est la traduction en C de ce qu'OCaml obtient gratuitement par l'immuabilité.

Les deux variables hg et hd dans hauteur : écrire directement 1 + max(hauteur(a->gauche), hauteur(a->droit)) avec un max défini par macro évaluerait deux fois l'un des deux appels, et transformerait un $\Theta (n)$ en $\Theta (2^h)$. C'est un des rares endroits où une variable temporaire est une nécessité de complexité et non de lisibilité.

L'ordre des tests dans feuilles : le test a == NULL vient en premier, sans quoi a->gauche déréférencerait NULL. C'est l'usage de l'évaluation paresseuse comme garde, vu au chapitre chap:langage-c, transposé à une suite de if.

La terminaison. Elle est acquise par le même argument qu'en OCaml : les appels portent sur a->gauche et a->droit, strictement plus petits pour l'ordre induit (chapitre chap:induction), qui est bien fondé. Mais la précondition « aucun cycle » devient ici une vraie obligation : rien n'empêche en C d'écrire a->gauche = a, et la fonction bouclerait jusqu'au débordement de pile. En OCaml, le type arbre construit avec Noeud ne peut pas former de cycle. C'est la précondition que le langage n'assure plus, et qu'il faut donc écrire.

Mesure : sur l'arbre des exercices précédents, la version C affiche taille = 7, hauteur = 3, feuilles = 3 — identique à la version OCaml — et ne fuit pas un octet.