Parcours en largeur des arbres binaires

Comprendre le principe du parcours en largeur d'un arbre binaire, son implémentation itérative à l'aide d'une file, et savoir le coder en Python et en C.

Prérequis

Notions de structures de données linéaires (file), récursivité, et représentations d'arbres binaires.

Définition — Parcours en largeur

Le parcours en largeur (ou Breadth-First Search, BFS) explore l'arbre niveau par niveau, de la gauche vers la droite à chaque niveau. On explore d'abord tous les nœuds du niveau 0 (racine), puis tous ceux du niveau 1, puis du niveau 2, etc.

Contrairement aux parcours en profondeur (infixe, préfixe, postfixe) qui utilisent une pile (implicitement via la récursivité), le parcours en largeur utilise une file (queue) pour mémoriser les nœuds à visiter. L'utilisation d'une file garantit que les nœuds du niveau \(N\) sont traités avant ceux du niveau \(N+1\).

Analogie

Le parcours en largeur est comme un balayage horizontal de l'arbre : on parcourt chaque étage de gauche à droite avant de descendre à l'étage suivant.

Exemple illustré

Parcours en largeur de l'arbre

Arbre

Parcours en largeur

6 → 4 → 8 → 3 → 7 → 9 → 14

Explication : Niveau 0 : 6, Niveau 1 : 4, 8, Niveau 2 : 3, 7, 9, 14

Algorithme du parcours en largeur

Algorithme itératif avec file

Initialiser une file vide.
Enfiler (ajouter) la racine de l'arbre dans la file.
Tant que la file n'est pas vide :
1. Défiler (retirer) le nœud en tête de file (nœud courant).
2. Traiter ce nœud (afficher sa valeur).
3. Si le nœud courant a un fils gauche, l'enfiler.
4. Si le nœud courant a un fils droit, l'enfiler.

Déroulement pas à pas

Étape	Description	Sortie	File d'attente
Initialisation	Enfiler la racine	-	`[6]`
1 (Niveau 0)	Défiler 6, enfiler ses fils (4, 8)	6	`[4, 8]`
2 (Niveau 1)	Défiler 4, enfiler ses fils (3, 7)	4	`[8, 3, 7]`
3 (Niveau 1)	Défiler 8, enfiler ses fils (9, 14)	8	`[3, 7, 9, 14]`
4 (Niveau 2)	Défiler 3 (pas de fils)	3	`[7, 9, 14]`
5 (Niveau 2)	Défiler 7 (pas de fils)	7	`[9, 14]`
6 (Niveau 2)	Défiler 9 (pas de fils)	9	`[14]`
7 (Niveau 2)	Défiler 14 (pas de fils)	14	`[]`

Implémentations

from collections import deque

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

def parcours_largeur(racine):
    """
    Parcours en largeur d'un arbre binaire (version POO)
    Utilise une file (deque) pour une complexité O(1) en push/pop
    """
    if racine is None:
        return
    
    file = deque()
    file.append(racine)
    
    while file:
        noeud = file.popleft()  # Défiler en tête (O(1))
        print(noeud.val, end=" ")
        
        if noeud.gauche:
            file.append(noeud.gauche)
        if noeud.droit:
            file.append(noeud.droit)

# Exemple d'utilisation
if __name__ == "__main__":
    # Construction de l'arbre
    #        6
    #       / \
    #      4   8
    #     / \ / \
    #    3  7 9 14
    
    racine = Noeud(6)
    racine.gauche = Noeud(4)
    racine.droit = Noeud(8)
    racine.gauche.gauche = Noeud(3)
    racine.gauche.droit = Noeud(7)
    racine.droit.gauche = Noeud(9)
    racine.droit.droit = Noeud(14)
    
    print("Parcours en largeur : ", end="")
    parcours_largeur(racine)
    print()

def parcours_largeur_liste(arbre):
    """
    Parcours en largeur avec représentation par liste
    Structure : [racine, gauche, droit]
    Un nœud vide est représenté par [].
    """
    if len(arbre) == 0:
        return
    
    file = []
    file.append(arbre)
    
    while file:
        noeud = file.pop(0)  # On retire le premier élément (O(n) - moins efficace)
        print(noeud[0], end=" ")
        
        if noeud[1] != []:  # Sous-arbre gauche non vide
            file.append(noeud[1])
        if noeud[2] != []:  # Sous-arbre droit non vide
            file.append(noeud[2])

# Version optimisée avec collections.deque
from collections import deque

def parcours_largeur_liste_opt(arbre):
    """Version optimisée avec deque (O(1) pour pop(0))"""
    if len(arbre) == 0:
        return
    
    file = deque()
    file.append(arbre)
    
    while file:
        noeud = file.popleft()
        print(noeud[0], end=" ")
        
        if noeud[1] != []:
            file.append(noeud[1])
        if noeud[2] != []:
            file.append(noeud[2])

# Exemple d'utilisation
if __name__ == "__main__":
    # Représentation par liste : [racine, gauche, droit]
    #        6
    #       / \
    #      4   8
    #     / \ / \
    #    3  7 9 14
    
    arbre = [6,
             [4,
              [3, [], []],
              [7, [], []]],
             [8,
              [9, [], []],
              [14, [], []]]]
    
    print("Parcours en largeur : ", end="")
    parcours_largeur_liste(arbre)
    print()

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

// Structure d'un nœud
struct Noeud {
    int val;
    struct Noeud *gauche;
    struct Noeud *droit;
};

// Structure d'une file simple (implémentation par liste chaînée)
struct FileNode {
    struct Noeud *noeud;
    struct FileNode *suivant;
};

struct File {
    struct FileNode *tete;
    struct FileNode *queue;
};

// Initialiser une file vide
struct File* creer_file() {
    struct File *f = (struct File*)malloc(sizeof(struct File));
    f->tete = NULL;
    f->queue = NULL;
    return f;
}

// Vérifier si la file est vide
int est_vide(struct File *f) {
    return f->tete == NULL;
}

// Enfiler un nœud
void enfiler(struct File *f, struct Noeud *noeud) {
    struct FileNode *nouveau = (struct FileNode*)malloc(sizeof(struct FileNode));
    nouveau->noeud = noeud;
    nouveau->suivant = NULL;
    
    if (est_vide(f)) {
        f->tete = nouveau;
        f->queue = nouveau;
    } else {
        f->queue->suivant = nouveau;
        f->queue = nouveau;
    }
}

// Défiler un nœud
struct Noeud* defiler(struct File *f) {
    if (est_vide(f)) return NULL;
    
    struct FileNode *temp = f->tete;
    struct Noeud *noeud = temp->noeud;
    f->tete = f->tete->suivant;
    
    if (f->tete == NULL) {
        f->queue = NULL;
    }
    
    free(temp);
    return noeud;
}

// Créer un nouveau nœud
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;
}

// Parcours en largeur
void parcours_largeur(struct Noeud *racine) {
    if (racine == NULL) return;
    
    struct File *file = creer_file();
    enfiler(file, racine);
    
    while (!est_vide(file)) {
        struct Noeud *noeud = defiler(file);
        printf("%d ", noeud->val);
        
        if (noeud->gauche != NULL) {
            enfiler(file, noeud->gauche);
        }
        if (noeud->droit != NULL) {
            enfiler(file, noeud->droit);
        }
    }
    
    free(file);
}

int main() {
    // Construction de l'arbre
    //        6
    //       / \
    //      4   8
    //     / \ / \
    //    3  7 9 14
    
    struct Noeud *racine = creer_noeud(6);
    racine->gauche = creer_noeud(4);
    racine->droit = creer_noeud(8);
    racine->gauche->gauche = creer_noeud(3);
    racine->gauche->droit = creer_noeud(7);
    racine->droit->gauche = creer_noeud(9);
    racine->droit->droit = creer_noeud(14);
    
    printf("Parcours en largeur : ");
    parcours_largeur(racine);
    printf("\n");
    
    return 0;
}

Sortie

Parcours en largeur : 6 4 8 3 7 9 14

Comparaison avec les parcours en profondeur

Critère	Parcours en largeur (BFS)	Parcours en profondeur (DFS)
Structure utilisée	File (Queue)	Pile (Stack) ou récursivité
Ordre de visite	Niveau par niveau (horizontal)	Profondeur d'abord (vertical)
Complexité temporelle	\(O(n)\)	\(O(n)\)
Complexité spatiale	\(O(w)\) où \(w\) = largeur max	\(O(h)\) où \(h\) = hauteur
Applications	Plus court chemin, niveau par niveau	Parcours complet, copie, destruction

Complexité spatiale

Pour un arbre binaire parfait de hauteur \(h\), la file contient au maximum \(2^{h-1}\) nœuds (le dernier niveau). La complexité spatiale est donc \(O(n)\) dans le pire cas (arbre parfait).

Applications du parcours en largeur

Affichage par niveaux : Visualisation de la structure hiérarchique.
Plus court chemin : Dans un graphe non pondéré, BFS trouve le chemin le plus court entre deux nœuds.
Arbre binaire complet : Vérifier si un arbre est complet.
Arbre binaire parfait : Vérifier si un arbre est parfait.
Calcul de la largeur maximale : Trouver le niveau avec le plus grand nombre de nœuds.
Affichage en zigzag : Parcours en largeur alternant gauche→droite et droite→gauche.

Conseils pratiques

En Python, utilisez collections.deque pour une file efficace (popleft() en \(O(1)\)).
Évitez list.pop(0) qui est en \(O(n)\) et ralentit considérablement le parcours.
En C, implémentez votre propre file avec une liste chaînée ou utilisez un tableau circulaire.
Pour les très grands arbres, BFS peut consommer beaucoup de mémoire (tous les nœuds d'un niveau).

Variantes du parcours en largeur

Parcours par niveaux avec séparation

On peut modifier l'algorithme pour afficher chaque niveau sur une ligne distincte :

from collections import deque

def parcours_par_niveaux(racine):
    """Affiche chaque niveau sur une ligne séparée"""
    if racine is None:
        return
    
    file = deque()
    file.append(racine)
    niveau = 0
    
    while file:
        taille_niveau = len(file)
        print(f"Niveau {niveau} : ", end="")
        
        for _ in range(taille_niveau):
            noeud = file.popleft()
            print(noeud.val, end=" ")
            
            if noeud.gauche:
                file.append(noeud.gauche)
            if noeud.droit:
                file.append(noeud.droit)
        
        print()  # Nouvelle ligne après le niveau
        niveau += 1

void parcours_par_niveaux(struct Noeud *racine) {
    if (racine == NULL) return;
    
    struct File *file = creer_file();
    enfiler(file, racine);
    int niveau = 0;
    
    while (!est_vide(file)) {
        // Compter le nombre de nœuds dans le niveau courant
        int taille_niveau = 0;
        struct FileNode *temp = file->tete;
        while (temp != NULL) {
            taille_niveau++;
            temp = temp->suivant;
        }
        
        printf("Niveau %d : ", niveau);
        
        for (int i = 0; i < taille_niveau; i++) {
            struct Noeud *noeud = defiler(file);
            printf("%d ", noeud->val);
            
            if (noeud->gauche != NULL) {
                enfiler(file, noeud->gauche);
            }
            if (noeud->droit != NULL) {
                enfiler(file, noeud->droit);
            }
        }
        
        printf("\n");
        niveau++;
    }
}

Sortie (parcours par niveaux)

Niveau 0 : 6
Niveau 1 : 4 8
Niveau 2 : 3 7 9 14

L'essentiel en bref

Points clés à retenir

Le parcours en largeur explore l'arbre niveau par niveau, de gauche à droite.
Il utilise une file (FIFO) pour mémoriser les nœuds à traiter.
Complexité temporelle : \(O(n)\) où \(n\) est le nombre de nœuds.
Complexité spatiale : \(O(w)\) où \(w\) est la largeur maximale de l'arbre.
Applications : plus court chemin, vérification d'arbre complet, affichage par niveaux.
En Python, privilégier collections.deque pour une file efficace.
En C, implémenter une file avec liste chaînée ou tableau circulaire.

Attention

Pour un arbre très large (ex: arbre parfait de grande hauteur), le parcours en largeur peut consommer beaucoup de mémoire car la file contient tous les nœuds du dernier niveau, soit environ \(n/2\) nœuds.

Un peu d'histoire

Le parcours en largeur (BFS) a été formalisé par Edward F. Moore dans les années 1950 pour résoudre le problème du labyrinthe. Il a ensuite été popularisé par Edsger Dijkstra qui l'a utilisé comme base pour son célèbre algorithme du plus court chemin. En algorithmique des graphes, BFS est l'un des algorithmes fondamentaux avec DFS.

Sortie

// La sortie apparaîtra ici…

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

Parcours en largeur des arbres binaires