Terminale NSI — Arbres

Séance 2 — Parcourir un arbre

Préfixe, infixe, suffixe, largeur · 2h

1. Les trois parcours en profondeur

def parcours_prefixe(A):    # racine, gauche, droite
    if A is not None:
        print(A.etiquette)
        parcours_prefixe(A.gauche)
        parcours_prefixe(A.droit)

def parcours_infixe(A):     # gauche, racine, droite
    if A is not None:
        parcours_infixe(A.gauche)
        print(A.etiquette)
        parcours_infixe(A.droit)

def parcours_suffixe(A):    # gauche, droite, racine
    if A is not None:
        parcours_suffixe(A.gauche)
        parcours_suffixe(A.droit)
        print(A.etiquette)

2. Exercice 1 — Dérouler les trois parcours à la main

Sur l'arbre fourni : a) ordre préfixe. b) ordre infixe. c) ordre suffixe.

Voir la réponse
Préfixe : A, B, C, E, D, F, G, I, H, J
Infixe : C, E, B, D, A, I, G, F, H, J
Suffixe : E, C, D, B, I, G, J, H, F, A

3. Exercice 2 — Le parcours en largeur (BFS)

from collections import deque

def parcours_largeur(A):
    if A is None:
        return
    f = deque()
    f.append(A)
    while f:
        x = f.popleft()
        print(x.etiquette)
        if x.gauche is not None:
            f.append(x.gauche)
        if x.droit is not None:
            f.append(x.droit)

a) Déroule à la main. b) Teste en Python. c) Pourquoi une file et pas une pile ?

Voir la réponse
Ordre : A, B, F, C, D, G, H, E, I, J — niveau par niveau.
Une pile (LIFO) traiterait en priorité les nœuds les plus récemment découverts, produisant un parcours en profondeur au lieu d'un parcours en largeur.

4. Exercice 3 — Encoder / décoder en notation parenthésée

def affiche(A):
    if A is None:
        return ""
    return "(" + affiche(A.gauche) + str(A.etiquette) + affiche(A.droit) + ")"

a) Teste sur A(B(C), D) → ((B(C))A(D)). b) Dessine l'arbre de (1((2)3)). c) Vérifie ta reconstruction.

Voir la réponse
Pour (1((2)3)) : racine 1 (sans fils gauche), fils droit 3, qui a pour fils gauche 2. La notation parenthésée conserve toute l'information nécessaire pour une reconstruction unique.

5. Exercice 4 — Affichage indenté façon explorateur de fichiers

Écris une fonction qui affiche l'arbre avec indentation croissante selon la profondeur.

Voir la réponse
def affiche_arborescence(A, indentation=""):
    if A is not None:
        print(f"{indentation}{A.etiquette}")
        affiche_arborescence(A.gauche, indentation + "  ")
        affiche_arborescence(A.droit, indentation + "  ")
C'est une variante du parcours préfixe : on affiche avant d'explorer.

Exercices défis (bonus)

Défi 1 — Plusieurs arbres, même parcours infixe défi
Voir la réponse
Peigne gauche (3, 2, 1) et arbre complet (2 racine, 1 gauche, 3 droit) donnent tous deux 1, 2, 3 en infixe. Le parcours infixe seul ne suffit donc pas à reconstruire un arbre de façon unique.
Défi 2 — Comparer deux arbres défi
Voir la réponse
def __eq__(self, autre):
    if self is None and autre is None:
        return True
    if self is None or autre is None:
        return False
    return (self.etiquette == autre.etiquette and
            self.gauche == autre.gauche and self.droit == autre.droit)