Parcours en profondeur des arbres binaires

Maîtriser les trois méthodes de parcours en profondeur d'un arbre binaire (infixe, préfixe, postfixe) et savoir les implémenter en Python (POO et listes) ainsi qu'en C.

Prérequis

Notions de récursivité, structures de données arborescentes, pointeurs en C, classes Python.

Définition — Parcours en profondeur

Le parcours en profondeur (Depth-First Search, DFS) d'un arbre binaire consiste à explorer chaque nœud en descendant jusqu'aux feuilles avant de remonter. Il existe trois méthodes principales, selon l'ordre de visite de la racine par rapport aux sous-arbres.

Il existe trois méthodes de parcours d'un arbre binaire :

Parcours infixe (LNR) : fils gauche → racine → fils droit
Parcours préfixe (NLR) : racine → fils gauche → fils droit
Parcours postfixe (LRN) : fils gauche → fils droit → racine

Implémentation

Ces parcours peuvent être réalisés en utilisant une pile, soit de manière explicite (itératif), soit implicitement via une procédure récursive. L'approche récursive est naturelle car la structure de l'arbre est elle-même récursive.

Arbre binaire exemple pour les parcours

Parcours infixe (LNR)

Algorithme

Parcourir le sous-arbre gauche (appel récursif)
Visiter la racine
Parcourir le sous-arbre droit (appel récursif)

Algorithme infixe(Noeud):
    si Noeud == NULL:
        retourner
    infixe(Noeud.gauche)
    visiter(Noeud.val)
    infixe(Noeud.droit)

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

def parcours_infixe(racine):
    """Parcours infixe (LNR) - version POO"""
    if racine is None:
        return
    
    parcours_infixe(racine.gauche)
    print(racine.val, end=" ")
    parcours_infixe(racine.droit)

def parcours_infixe_liste(arbre):
    """
    Parcours infixe avec représentation par liste
    Structure : [racine, gauche, droit]
    """
    if len(arbre) == 0:
        return []
    return parcours_infixe_liste(arbre[1]) + [arbre[0]] + parcours_infixe_liste(arbre[2])

#include <stdio.h>
#include <stdlib.h>

struct Noeud {
    int val;
    struct Noeud *gauche;
    struct Noeud *droit;
};

void parcours_infixe(struct Noeud *racine) {
    if (racine == NULL) return;
    
    parcours_infixe(racine->gauche);
    printf("%d ", racine->val);
    parcours_infixe(racine->droit);
}

Exemple d'exécution

Arbre

        30
       /  \
      16   40
     /  \    \
    9   20    50

Parcours infixe

9 16 20 30 40 50

Propriété importante : Dans un arbre binaire de recherche (ABR), le parcours infixe donne les nœuds dans l'ordre croissant.

Parcours préfixe (NLR)

Algorithme

Visiter la racine
Parcourir le sous-arbre gauche (appel récursif)
Parcourir le sous-arbre droit (appel récursif)

Algorithme prefixe(Noeud):
    si Noeud == NULL:
        retourner
    visiter(Noeud.val)
    prefixe(Noeud.gauche)
    prefixe(Noeud.droit)

def parcours_prefixe(racine):
    """Parcours préfixe (NLR) - version POO"""
    if racine is None:
        return
    
    print(racine.val, end=" ")
    parcours_prefixe(racine.gauche)
    parcours_prefixe(racine.droit)

def parcours_prefixe_liste(arbre):
    """
    Parcours préfixe avec représentation par liste
    Structure : [racine, gauche, droit]
    """
    if len(arbre) == 0:
        return []
    return [arbre[0]] + parcours_prefixe_liste(arbre[1]) + parcours_prefixe_liste(arbre[2])

void parcours_prefixe(struct Noeud *racine) {
    if (racine == NULL) return;
    
    printf("%d ", racine->val);
    parcours_prefixe(racine->gauche);
    parcours_prefixe(racine->droit);
}

Exemple d'exécution

Arbre

        30
       /  \
      16   40
     /  \    \
    9   20    50

Parcours préfixe

30 16 9 20 40 50

Applications :

Créer une copie de l'arbre
Obtenir l'expression préfixe (notation polonaise) d'un arbre d'expression
Sérialiser un arbre pour le sauvegarder

Parcours postfixe (LRN)

Algorithme

Parcourir le sous-arbre gauche (appel récursif)
Parcourir le sous-arbre droit (appel récursif)
Visiter la racine

Algorithme postfixe(Noeud):
    si Noeud == NULL:
        retourner
    postfixe(Noeud.gauche)
    postfixe(Noeud.droit)
    visiter(Noeud.val)

def parcours_postfixe(racine):
    """Parcours postfixe (LRN) - version POO"""
    if racine is None:
        return
    
    parcours_postfixe(racine.gauche)
    parcours_postfixe(racine.droit)
    print(racine.val, end=" ")

def parcours_postfixe_liste(arbre):
    """
    Parcours postfixe avec représentation par liste
    Structure : [racine, gauche, droit]
    """
    if len(arbre) == 0:
        return []
    return parcours_postfixe_liste(arbre[1]) + parcours_postfixe_liste(arbre[2]) + [arbre[0]]

void parcours_postfixe(struct Noeud *racine) {
    if (racine == NULL) return;
    
    parcours_postfixe(racine->gauche);
    parcours_postfixe(racine->droit);
    printf("%d ", racine->val);
}

Exemple d'exécution

Arbre

        30
       /  \
      16   40
     /  \    \
    9   20    50

Parcours postfixe

9 20 16 50 40 30

Applications :

Supprimer un arbre (libérer la mémoire) — on supprime les enfants avant la racine
Obtenir l'expression postfixe (notation polonaise inverse) d'un arbre d'expression
Calculer la hauteur ou la taille d'un arbre

Exemple complet d'implémentation

Exemple complet

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

# Construction de l'arbre
#        30
#       /  \
#      16   40
#     /  \    \
#    9   20    50

racine = Noeud(30)
racine.gauche = Noeud(16)
racine.droit = Noeud(40)
racine.gauche.gauche = Noeud(9)
racine.gauche.droit = Noeud(20)
racine.droit.droit = Noeud(50)

print("Parcours infixe   : ", end="")
parcours_infixe(racine)
print()

print("Parcours préfixe  : ", end="")
parcours_prefixe(racine)
print()

print("Parcours postfixe : ", end="")
parcours_postfixe(racine)
print()

# Représentation par liste : [racine, gauche, droit]
#        30
#       /  \
#      16   40
#     /  \    \
#    9   20    50

arbre = [30,
         [16,
          [9, [], []],
          [20, [], []]],
         [40,
          [],
          [50, [], []]]]

print("Parcours infixe   :", parcours_infixe_liste(arbre))
print("Parcours préfixe  :", parcours_prefixe_liste(arbre))
print("Parcours postfixe :", parcours_postfixe_liste(arbre))

#include <stdio.h>
#include <stdlib.h>

struct Noeud {
    int val;
    struct Noeud *gauche;
    struct Noeud *droit;
};

struct Noeud* creer_noeud(int val) {
    struct Noeud* nouveau = (struct Noeud*)malloc(sizeof(struct Noeud));
    nouveau->val = val;
    nouveau->gauche = NULL;
    nouveau->droit = NULL;
    return nouveau;
}

int main() {
    // Construction de l'arbre
    //        30
    //       /  \
    //      16   40
    //     /  \    \
    //    9   20    50
    
    struct Noeud* racine = creer_noeud(30);
    racine->gauche = creer_noeud(16);
    racine->droit = creer_noeud(40);
    racine->gauche->gauche = creer_noeud(9);
    racine->gauche->droit = creer_noeud(20);
    racine->droit->droit = creer_noeud(50);
    
    printf("Parcours infixe   : ");
    parcours_infixe(racine);
    printf("\n");
    
    printf("Parcours préfixe  : ");
    parcours_prefixe(racine);
    printf("\n");
    
    printf("Parcours postfixe : ");
    parcours_postfixe(racine);
    printf("\n");
    
    return 0;
}

Sortie

Parcours infixe   : 9 16 20 30 40 50
Parcours préfixe  : 30 16 9 20 40 50
Parcours postfixe : 9 20 16 50 40 30

Comparaison des trois parcours

Parcours	Ordre	Applications principales
Infixe (LNR)\\	Gauche → Racine → Droit\\	Affichage trié d'un ABR Obtenir les valeurs en ordre croissant
Préfixe (NLR)\\	Racine → Gauche → Droit\\	Copie/sérialisation d'un arbre Expression préfixe (notation polonaise)
Postfixe (LRN)\\	Gauche → Droit → Racine\\	Libération de la mémoire (destruction) Expression postfixe (RPN) Calcul de hauteur/taille

L'essentiel en bref

Points clés à retenir

Les trois parcours en profondeur sont récursifs par nature et s'implémentent simplement avec des appels récursifs.
Infixe (LNR) : gauche → racine → droit — donne l'ordre croissant dans un ABR.
Préfixe (NLR) : racine → gauche → droit — utile pour copier/sérialiser.
Postfixe (LRN) : gauche → droit → racine — utile pour supprimer ou évaluer.
En Python, deux représentations possibles : POO (classe Noeud) ou listes imbriquées.
En C, on utilise des structures avec pointeurs vers les enfants.

Conseils pratiques

Toujours vérifier si le nœud est NULL/None avant de le parcourir (cas d'arrêt).
La version récursive est la plus naturelle, mais pour de très grands arbres, une version itérative (pile explicite) peut être préférable.
Pour les arbres binaires de recherche, le parcours infixe est votre meilleur allié pour les affichages triés.
Pour libérer la mémoire d'un arbre en C, utilisez un parcours postfixe pour supprimer les enfants avant la racine.

Attention à la récursivité

La récursivité utilise la pile d'appels. Pour un arbre très profond (hauteur > 1000), vous risquez un débordement de pile. Dans ce cas, préférez une implémentation itérative avec une pile explicite.

Un peu d'histoire

Les notations préfixe, infixe et postfixe ont été introduites par le mathématicien polonais Jan Łukasiewicz dans les années 1920. La notation préfixe est parfois appelée notation polonaise, et la notation postfixe notation polonaise inverse (RPN). Ces notations sont utilisées en informatique pour évaluer des expressions sans parenthèses et sont implémentées via des piles.

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Précédent Types d'arbre binaire

Suivant Parcours en largeur d'un arbre binaire

Discussion (0)

Soyez le premier à laisser un commentaire !

Laisser un commentaire

Votre commentaire sera visible après modération.

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Parcours en profondeur des arbres binaires