DS 6 (MP2I 2022-2023) — Arbres n-aires en C

Devoir surveillé · MP2I · 2022-2023 · partie 1 du DS 6 (4 h au total)

Cours : Arbres

Autres parties : 2 et 4. Recherche trichotomique, médians · 3. Table de hachage

Tout document interdit. Tout dispositif électronique interdit.

On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles.

1. Arbres n-aires en C

On va représenter ici des arbres n-aires en C.

On considère le type suivant :

struct noeud {
    int valeur;
    int arite;
    struct noeud *enfants;
};

typedef struct noeud arbre;

Ainsi, chaque nœud contiendra : sa valeur, c'est-à-dire l'étiquette du nœud, son arité, c'est-à-dire son nombre de nœuds enfants et le tableau de ses enfants.

Les nœuds d'arité nulle sont les feuilles.

Question 1

Quelle différence avec le type vu en OCaml pour la même structure ? Expliquer.

Corrigé

On ne peut pas connaître la taille d'un tableau passé par pointeur comme dans cette structure. Il est donc nécessaire d'avoir également l'arité dans les nœuds.

On remarque qu'on aurait aussi pu faire une liste chaînée de nœuds enfants, mais cela rajoute beaucoup de complexité dans la gestion de la mémoire.

Question 2

Expliquer comment on peut représenter l'arbre vide en considérant des éléments du type arbre *.

Corrigé

Il suffit de le représenter avec le pointeur NULL. Une subtilité ici, l'arbre vide n'est jamais un sous-arbre. On est plus proche d'un type optionnel comme en OCaml.

Question 3

Écrire une fonction de prototype

int taille(arbre *a);

qui renvoie le nombre de nœuds d'un arbre.

Corrigé

int taille(arbre *a) {
    if (a == NULL)
        return 0;

    int t = 1;
    for (int i = 0; i < a->arite; i++) {
        t += taille(&a->enfants[i]);
    }
    return t;
}

Question 4

Écrire une fonction qui affiche tous les nœuds dans un parcours préfixe.

void affiche(arbre *a);

Corrigé

void affiche(arbre *a) {
    if (a == NULL)
        return;

    printf("%d\n", a->valeur);
    for (int i = 0; i < a->arite; i++) {
        affiche(&a->enfants[i]);
    }
}

Question 5

Écrire une fonction de prototype

int somme(arbre *a);

qui renvoie la somme des étiquettes des nœuds dans l'arbre.

Corrigé

int somme(arbre *a) {
    if (a == NULL)
        return 0;

    int s = a->valeur;
    for (int i = 0; i < a->arite; i++) {
        s += somme(&a->enfants[i]);
    }
    return s;
}

Question 6

On souhaite libérer la mémoire occupée par un arbre et Justin Topain, votre camarade, propose le code suivant :

void libere(arbre *a) {
    free(a);
    for (int i = 0; i < a->arite; i++) {
        free(a->enfants[i]);
    }
}

Indiquer les erreurs logiques dans ce code en expliquant pourquoi elles en sont. Proposer une version correcte de cette fonction.

Corrigé

Un problème ici est de libérer a avant d'accéder à a->enfants ou a->arite. De plus, il faudrait gérer l'arbre vide.

On a également un problème avec le passage par pointeur, a->enfants[i] est un arbre et pas un arbre *. Notons que c'est le même problème dans les questions précédentes.

Autre problème, cette fonction doit être récursive pour ne pas libérer qu'un nœud et ses enfants.

Enfin, les enfants d'un nœud sont rangés dans un seul tableau alloué a->enfants : c'est ce tableau qu'il faut libérer (après avoir libéré les tableaux des descendants), et non chacune de ses cases. On suppose ici que la racine a été allouée par malloc et que chaque tableau enfants est alloué par malloc (ou vaut NULL pour une feuille).

// libère les tableaux d'enfants de tous les descendants de a, sans libérer a
void libere_enfants(arbre *a) {
    for (int i = 0; i < a->arite; i++) {
        libere_enfants(&a->enfants[i]);
    }
    free(a->enfants);
}

void libere(arbre *a) {
    if (a == NULL)
        return;
    libere_enfants(a);
    free(a);
}