Chapitre 5 - Entraînement : Les arbres

Arbres et mesures

Exercice 1 - Mesures d'un arbre binaire

On considère l'arbre binaire suivant :

         12
        /  \
       6    18
      / \     \
     3   8    25
        /
       7

a. Donner la racine, les feuilles et les nœuds internes.

b. Quelle est la taille ? La hauteur ?

c. Quelle est la profondeur du nœud 7 ? Du nœud 18 ?

d. Construire cet arbre en Python et vérifier avec les fonctions taille() et hauteur().

Solution

a. Racine : 12. Feuilles : 3, 7, 25. Nœuds internes : 12, 6, 18, 8.

b. Taille = 7. Hauteur = 3 (chemin 12 → 6 → 8 → 7).

c. Profondeur de 7 : 3 (3 arêtes). Profondeur de 18 : 1.

class Noeud:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche
        self.droit = droit

def taille(a):
    if a is None: return 0
    return 1 + taille(a.gauche) + taille(a.droit)

def hauteur(a):
    if a is None: return -1
    return 1 + max(hauteur(a.gauche), hauteur(a.droit))

arbre = Noeud(12,
    Noeud(6, Noeud(3), Noeud(8, Noeud(7))),
    Noeud(18, None, Noeud(25))
)
print(taille(arbre))   # 7
print(hauteur(arbre))  # 3

Parcours et arbres binaires de recherche

Exercice 2 - Taille, hauteur et parcours

Soit l'arbre binaire suivant :

        15
       /  \
      9    20
     / \     \
    4   12    25
   /   /
  2   10

a. Donner la taille et la hauteur de cet arbre.

b. Donner le résultat de chaque parcours : préfixe, infixe, suffixe, largeur.

c. Cet arbre est-il un ABR ? Justifier.

Solution

a. Taille = 7 nœuds. Hauteur = 3 (chemin 15 → 9 → 4 → 2).

Préfixe (R-G-D) : 15, 9, 4, 2, 12, 10, 20, 25
Infixe (G-R-D) : 2, 4, 9, 10, 12, 15, 20, 25
Suffixe (G-D-R) : 2, 4, 10, 12, 9, 25, 20, 15
Largeur : 15, 9, 20, 4, 12, 25, 2, 10

c. Oui, c'est un ABR : le parcours infixe donne les valeurs dans l'ordre croissant, et pour chaque nœud, les valeurs à gauche sont inférieures et celles à droite sont supérieures.

Exercice 3 - Construction d'un ABR

a. Construire l'ABR obtenu en insérant successivement les valeurs : 7, 3, 11, 1, 5, 9, 13, 4, 8.

b. Quelle est la hauteur de l'arbre obtenu ?

c. En insérant les mêmes valeurs dans un autre ordre, peut-on obtenir un arbre de hauteur différente ? Donner un exemple.

Solution

b. Hauteur = 3.

c. Oui. En insérant dans l'ordre croissant 1, 3, 4, 5, 7, 8, 9, 11, 13, on obtient un arbre filiforme de hauteur 8 (dégénéré en liste). L'ordre d'insertion détermine la forme de l'ABR.

Exercice 4 - Fonctions récursives sur les arbres

Écrire les fonctions suivantes :

a. somme(arbre) : renvoie la somme de toutes les valeurs.

b. recherche(arbre, valeur) : renvoie True si la valeur est dans l'arbre (arbre quelconque, pas un ABR).

c. miroir(arbre) : renvoie un nouvel arbre qui est l'image miroir (gauche ↔ droite).

Solution

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

def recherche(arbre, valeur):
    if arbre is None:
        return False
    if arbre.valeur == valeur:
        return True
    return recherche(arbre.gauche, valeur) or recherche(arbre.droit, valeur)

def miroir(arbre):
    if arbre is None:
        return None
    return Noeud(arbre.valeur, miroir(arbre.droit), miroir(arbre.gauche))

Activités

Activité 1 - Arbre d'expressions arithmétiques

Modéliser une expression arithmétique sous forme d'arbre binaire (les feuilles sont les nombres, les nœuds internes les opérateurs). Écrire une fonction récursive evaluer(arbre) qui calcule le résultat.

Tester avec l'expression (3 + 5) × (7 - 2).

Solution

class Noeud:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche
        self.droit = droit

def evaluer(arbre):
    if arbre.gauche is None and arbre.droit is None:
        return float(arbre.valeur)
    g = evaluer(arbre.gauche)
    d = evaluer(arbre.droit)
    if arbre.valeur == '+': return g + d
    if arbre.valeur == '-': return g - d
    if arbre.valeur == '*': return g * d
    if arbre.valeur == '/': return g / d

def infixe(arbre):
    if arbre.gauche is None:
        return str(arbre.valeur)
    return f"({infixe(arbre.gauche)} {arbre.valeur} {infixe(arbre.droit)})"

# (3 + 5) * (7 - 2)
expr = Noeud('*',
    Noeud('+', Noeud(3), Noeud(5)),
    Noeud('-', Noeud(7), Noeud(2))
)

print(infixe(expr))    # ((3 + 5) * (7 - 2))
print(evaluer(expr))   # 40.0

Activité 2 - Visualiser les parcours d'arbres

Écrire un programme qui construit un arbre binaire et affiche visuellement les étapes de chaque type de parcours (préfixe, infixe, suffixe, largeur), en numérotant l'ordre de visite.

Solution

from collections import deque

class Noeud:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche
        self.droit = droit

def afficher_parcours(nom, resultat):
    print(f"{nom} :")
    for i, val in enumerate(resultat, 1):
        print(f"  Étape {i} : visite du nœud {val}")
    print()

arbre = Noeud(15,
    Noeud(9, Noeud(4, Noeud(2)), Noeud(12, Noeud(10))),
    Noeud(20, None, Noeud(25))
)

def prefixe(a):
    if a is None: return []
    return [a.valeur] + prefixe(a.gauche) + prefixe(a.droit)

def infixe(a):
    if a is None: return []
    return infixe(a.gauche) + [a.valeur] + infixe(a.droit)

def suffixe(a):
    if a is None: return []
    return suffixe(a.gauche) + suffixe(a.droit) + [a.valeur]

def largeur(a):
    if a is None: return []
    res, file = [], deque([a])
    while file:
        n = file.popleft()
        res.append(n.valeur)
        if n.gauche: file.append(n.gauche)
        if n.droit: file.append(n.droit)
    return res

afficher_parcours("Préfixe", prefixe(arbre))
afficher_parcours("Infixe", infixe(arbre))
afficher_parcours("Suffixe", suffixe(arbre))
afficher_parcours("Largeur", largeur(arbre))