Arbres binaires

On va considérer le type suivant pour des arbres binaires en C :

struct noeud {
    struct noeud *gauche;
    struct noeud *droite;
    int valeur;
};

typedef struct noeud arbre;

L'arbre vide est alors représenté par la valeur NULL, et un arbre est manipulé par un pointeur arbre * vers sa racine, alloué sur le tas.

Pour construire des arbres de test, on pourra utiliser la fonction suivante :

arbre *noeud(arbre *g, int v, arbre *d)
{
    arbre *a = malloc(sizeof(arbre));
    a->gauche = g;
    a->valeur = v;
    a->droite = d;
    return a;
}

Par exemple, l'arbre de racine 5, de fils gauche 1 (lui-même de fils droit 4) et de fils droit 9 (de fils 7 et 20) s'obtient avec :

arbre *a = noeud(noeud(NULL, 1, noeud(NULL, 4, NULL)), 5,
                 noeud(noeud(NULL, 7, NULL), 9, noeud(NULL, 20, NULL)));

Question 1

Écrire une fonction de prototype

int taille(arbre *a);

qui renvoie la taille d'un arbre binaire, c'est-à-dire son nombre de nœuds.

Corrigé

int taille(arbre *a)
{
    if (a == NULL)
        return 0;
    return 1 + taille(a->gauche) + taille(a->droite);
}

Question 2

Écrire une fonction de prototype

int hauteur(arbre *a);

qui renvoie la hauteur d'un arbre binaire.

Corrigé

Avec la convention du cours, l'arbre vide est de hauteur \(-1\) (une feuille est donc de hauteur 0).

int max(int a, int b)
{
    return a > b ? a : b;
}

int hauteur(arbre *a)
{
    if (a == NULL)
        return -1;
    return 1 + max(hauteur(a->gauche), hauteur(a->droite));
}

Sur l'exemple, on obtient une taille de 6 et une hauteur de 2.

Question 3

Écrire une fonction de prototype

arbre *parfait(int n);

qui renvoie un arbre binaire parfait de hauteur n. On mettra des valeurs 1 comme étiquettes partout pour simplifier.

Corrigé

Un arbre parfait de hauteur \(n \ge 0\) a pour sous-arbres deux arbres parfaits de hauteur \(n-1\) ; l'arbre parfait de hauteur \(-1\) est l'arbre vide.

arbre *parfait(int n)
{
    if (n == -1)
        return NULL;
    return noeud(parfait(n - 1), 1, parfait(n - 1));
}

On vérifie par récurrence que parfait(n) a \(2^{n+1} - 1\) nœuds. Les deux appels récursifs sont nécessaires : avec un seul appel dont on réutiliserait le résultat pour les deux fils, les deux sous-arbres seraient partagés, et la libération de l'arbre libérerait deux fois les mêmes nœuds.

Question 4

Écrire une fonction qui libère toute la mémoire occupée par un arbre binaire.

Corrigé

void libere(arbre *a)
{
    if (a != NULL)
    {
        libere(a->gauche);
        libere(a->droite);
        free(a); // en dernier : après free, on ne peut plus lire a->gauche
    }
}

Parcours

Question 5

Écrire des fonctions réalisant un affichage des étiquettes des nœuds suivant les trois ordres : préfixe, postfixe et infixe.

Corrigé

Seule la position de l'affichage par rapport aux deux appels récursifs change.

void affiche_prefixe(arbre *a)
{
    if (a != NULL)
    {
        printf("%d ", a->valeur);
        affiche_prefixe(a->gauche);
        affiche_prefixe(a->droite);
    }
}

void affiche_infixe(arbre *a)
{
    if (a != NULL)
    {
        affiche_infixe(a->gauche);
        printf("%d ", a->valeur);
        affiche_infixe(a->droite);
    }
}

void affiche_postfixe(arbre *a)
{
    if (a != NULL)
    {
        affiche_postfixe(a->gauche);
        affiche_postfixe(a->droite);
        printf("%d ", a->valeur);
    }
}

Sur l'exemple, on obtient respectivement 5 1 4 9 7 20, 1 4 5 7 9 20 et 4 1 7 20 9 5.

Comme les nœuds sont mutables, on peut faire des modifications en place.

Question 6

Écrire une fonction qui incrémente toutes les étiquettes dans un arbre.

Corrigé

void incremente(arbre *a)
{
    if (a != NULL)
    {
        a->valeur = a->valeur + 1;
        incremente(a->gauche);
        incremente(a->droite);
    }
}

La fonction ne renvoie rien : elle modifie directement les nœuds accessibles depuis le pointeur a.