Exercices : arbres binaires

Exercice 1 — QCM : vocabulaire et propriétés des arbres

Pour chaque question, une seule réponse est correcte.

1. Quelle est la hauteur d’un arbre binaire réduit à sa racine (sans fils) ?

• A. \(-1\)
• B. 0
• C. 1
• D. indéfinie

Correction publiée après la séance.

2. Un arbre binaire de hauteur 3 peut contenir au maximum :

• A. 3 nœuds
• B. 7 nœuds
• C. 8 nœuds
• D. 15 nœuds

Correction publiée après la séance.

3. Quel parcours d’un ABR produit les valeurs dans l’ordre croissant ?

• A. préfixe (nœud, gauche, droit)
• B. infixe (gauche, nœud, droit)
• C. suffixe (gauche, droit, nœud)
• D. en largeur (niveau par niveau)

Correction publiée après la séance.

4. On cherche la valeur 42 dans un ABR équilibré contenant 1 000 nœuds. Le nombre maximal de comparaisons est environ :

• A. 10
• B. 42
• C. 500
• D. 1 000

Correction publiée après la séance.

5. On insère les valeurs 1, 2, 3, 4, 5 dans cet ordre dans un ABR vide. Quelle forme a l’arbre obtenu ?

• A. un arbre équilibré de hauteur 2
• B. un arbre peigne (dégénéré) vers la droite, de hauteur 4
• C. un arbre peigne vers la gauche, de hauteur 4
• D. un arbre aléatoire dont la forme dépend de l’implémentation

Correction publiée après la séance.

Exercice 2 — Exercice guidé : dérouler les parcours en profondeur

On considère l’arbre binaire suivant :

1. Recopier et compléter le tableau en indiquant l’ordre de visite pour chaque parcours :

2. Dérouler le parcours en largeur en complétant l’état de la file à chaque étape :

3. Quelle est la taille de cet arbre ? Sa hauteur ?

   Indice

   La taille est le nombre de nœuds. Pour la hauteur, compter le plus long chemin de la racine à une feuille, avec la convention du cours.

Correction publiée après la séance.

Exercice 3 — Exercice guidé : compléter des fonctions récursives à trous

On utilise la classe Arbre définie en cours (valeur, gauche, droit). Un arbre vide est représenté par None.

a) Compléter la fonction qui renvoie True si une valeur x est présente dans un arbre binaire quelconque (pas nécessairement un ABR) :

def contient(arbre, x):
    if arbre is None:
        return ...
    if arbre.valeur == x:
        return ...
    return contient(..., x) or contient(..., x)

b) Compléter la fonction qui renvoie la liste des feuilles d’un arbre binaire :

def liste_feuilles(arbre):
    if arbre is None:
        return ...
    if arbre.gauche is None and arbre.droit is None:
        return ...
    return liste_feuilles(...) + liste_feuilles(...)

c) Compléter la fonction qui renvoie le parcours préfixe sous forme de liste :

def prefixe_liste(arbre):
    if arbre is None:
        return []
    return [...] + prefixe_liste(...) + prefixe_liste(...)

d) Pour la fonction contient complétée en a), identifier, sans exécuter le code, les cas de base (quelles conditions arrêtent la récursion ?) et les appels récursifs (comment le problème se réduit-il ?).

Correction publiée après la séance.

Exercice 4 — Construire un ABR par insertions successives

On insère les valeurs suivantes, dans cet ordre, dans un ABR initialement vide : 8, 3, 10, 1, 6, 14, 4, 7, 13.

1. Dessiner l’ABR obtenu après chaque insertion (ou au minimum après les insertions de 8, 3, 10, 1, 6, et l’arbre final).

   Indice

   Chaque nouvelle valeur part de la racine : on descend à gauche si elle est plus petite que le nœud, à droite sinon, jusqu’à une place libre, où elle devient une feuille.

2. Donner la taille et la hauteur de l’ABR final.

   Indice

   Mêmes définitions qu’à l’exercice 2 : compter les nœuds, puis le plus long chemin de la racine à une feuille.

3. Effectuer le parcours infixe de l’ABR et vérifier qu’on obtient les valeurs dans l’ordre croissant.

   Indice

   Infixe : sous-arbre gauche, nœud, sous-arbre droit. Dans un ABR, tout le sous-arbre gauche est plus petit que le nœud, et tout le sous-arbre droit plus grand.

4. On cherche la valeur 7 dans cet ABR. Lister les comparaisons effectuées et le chemin suivi.

   Indice

   Partir de la racine et comparer 7 à chaque nœud rencontré : s’il est plus petit, descendre à gauche ; plus grand, à droite ; égal, la recherche s’arrête.

Correction publiée après la séance.

Exercice 5 — Programmer des fonctions sur les arbres

On utilise la classe Arbre du cours. Écrire les fonctions suivantes :

1. somme(arbre) : renvoie la somme de toutes les valeurs (entières) de l’arbre. Renvoie 0 si l’arbre est vide.

   Indice

   Arbre vide : 0. Sinon, la somme est la valeur de la racine, plus la somme du sous-arbre gauche, plus celle du sous-arbre droit.

   Code à copier puis compléter

   def somme(arbre):
       if arbre is None:
           return ...
       return arbre.valeur + somme(...) + somme(...)
   

2. miroir(arbre) : renvoie un nouvel arbre qui est le miroir de l’arbre donné (les sous-arbres gauche et droit sont échangés à chaque nœud).

   Indice

   Le miroir d’un arbre vide est vide. Sinon, créer un nouvel arbre de même valeur, dont le fils gauche est le miroir du sous-arbre droit, et le fils droit le miroir du sous-arbre gauche.

   Code à copier puis compléter

   def miroir(arbre):
       if arbre is None:
           return None
       return Arbre(arbre.valeur, miroir(...), miroir(...))
   

3. meme_structure(a1, a2) : renvoie True si les deux arbres ont la même structure (même forme), indépendamment des valeurs.

   Indice

   Deux arbres vides ont la même structure ; si un seul des deux est vide, non. Sinon, les sous-arbres gauches doivent avoir la même structure, et les sous-arbres droits aussi.

   Code à copier puis compléter

   def meme_structure(a1, a2):
       if a1 is None and a2 is None:
           return True
       if a1 is None or a2 is None:
           return ...
       return meme_structure(a1.gauche, ...) and meme_structure(..., ...)
   

Correction publiée après la séance.

Exercice 6 — Arbre d’expression arithmétique (synthèse)

Un arbre d’expression est un arbre binaire où les feuilles contiennent des nombres et les nœuds internes contiennent des opérateurs (+, -, *, /).

Par exemple, l’expression \((3 + 4) \times (8 - 2)\) est représentée par :

1. Dessiner l’arbre d’expression correspondant à \((5 + 1) \times 2 - (9 / 3)\).

   Indice

   La racine porte l’opération effectuée en dernier, ici la soustraction : son fils gauche représente \((5 + 1) \times 2\), et son fils droit \(9 / 3\).

2. Écrire une fonction récursive evaluer(arbre) qui évalue un arbre d’expression et renvoie le résultat du calcul.

   Indications :

   • si le nœud est une feuille (pas de fils), renvoyer sa valeur (c’est un nombre) ;
   • sinon, évaluer récursivement les deux sous-arbres et appliquer l’opérateur.
   Indice

   Le nœud est une feuille quand arbre.gauche is None and arbre.droit is None. Pour un opérateur, calculer g = evaluer(arbre.gauche) et d = evaluer(arbre.droit), puis choisir l’opération selon arbre.valeur.

   Code à copier puis compléter

   def evaluer(arbre):
       if arbre.gauche is None and arbre.droit is None:
           return arbre.valeur
       g = evaluer(arbre.gauche)
       d = evaluer(arbre.droit)
       if arbre.valeur == "+":
           return g + d
       elif arbre.valeur == "-":
           return ...
       elif arbre.valeur == "*":
           return ...
       else:
           return ...
   

3. Quel parcours correspond à la notation polonaise inversée (NPI) de l’expression ? Donner la NPI de l’arbre de la question 1.

   Indice

   En NPI, les deux opérandes s’écrivent avant l’opérateur : quel parcours visite le nœud après ses deux sous-arbres ?

4. Bonus. Écrire une fonction infixe_parenthesee(arbre) qui renvoie l’expression en notation infixe avec parenthèses. Par exemple, pour l’arbre ci-dessus : "((3+4)*(8-2))".

   Indice

   Une feuille donne str(arbre.valeur). Pour un opérateur, assembler "(", l’expression du sous-arbre gauche, l’opérateur, celle du sous-arbre droit, puis ")".

Correction publiée après la séance.