Parcours (Bac 🎯)

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

• le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
• le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
• l'article sur les arbres en NSI de Sébastien Hoarau
• le cours de mon collègue Pierre Duclosson
• le cours de Gilles Lassus
• le cours de Franck Chambon

🔖 Synthèse de ce qu'il faut retenir pour le bac

Parcours d'un arbre binaire

Point de cours 9

Un parcours d'un arbre binaire est un algorithme qui visite chaque noeud de l'arbre et lui applique un certain traitement (affichage, récupération de la valeur de l'élément stocké, de la profondeur ...). Le parcours peut traverser plusieurs fois un noeud mais le traitement est appliqué une seule fois pour chaque noeud.

Pour un arbre binaire on distingue deux principaux algorithmes de parcours :

• le parcours en profondeur
• le parcours en largeur

⏱️ Complexité

Si le nombre de fois où un algorithme de parcours traverse un noeud est borné, et si la complexité de traitement d'un noeud l'est aussi, alors un algorithme de parcours d'arbre binaire a une complexité temporelle linéaire par rapport à la taille de l'arbre. C'est le cas des algorithmes de parcours en profondeur et de parcours en largeur.

Parcours en profondeur d'un arbre binaire

Point de cours 10

Le parcours en profondeur d'un arbre binaire part de la racine et se dirige préférentiellement vers les feuilles en explorant les branches jusqu'au bout avant de remonter vers les noeuds déjà visités pour parcourir d'autres descendants. On visite les enfants d'un noeud avant ses frères.

L'acronyme anglais pour désigner le parcours en profondeur est DFS pour Depth First Search.

Exemple de parcours en profondeur d'un arbre binaire

Le parcours en profondeur exploite directement la nature récursive d'un arbre binaire, il est donc naturel de l'implémenter récursivement.

Le parcours en profondeur peut passer jusqu'à trois fois par un même noeud : découverte, remontée depuis le sous-arbre/fils gauche et remontée depuis le sous-arbre/fils droit. On distingue donc trois types de parcours en profondeur selon la position du traitement appliqué à l'élément stocké dans le noeud par rapport à l'exploration des sous-arbres/fils (gauche puis droite).

Parcours en profondeur préfixe, infixe ou suffixe/postfixe

parcours préfixeparcours infixeparcours suffixe/postfixe

Dans le parcours en profondeur préfixe, on traite l'élément stocké dans le noeud avant de parcourir les sous-arbres.

🐍 Script Python

def parcours_prefixe(arbre):
    if arbre is None: # cas de l'arbre vide
        return 
    traitement(arbre.racine) # on traite le noeud racine
    parcours_prefixe(arbre.gauche) # on parcourt récursivement le fils gauche
    parcours_prefixe(arbre.droit) # on parcourt récursivement le fils droit

Pour l'arbre binaire donné en exemple, avec un parcours préfixe, l'ordre de traitement des éléments stockés serait :

📋 Texte

A - L - O - R - G - I - T - M - E - H

Dans le parcours en profondeur infixe, on taite l'élément stocké dans le noeud entre le parcours du sous-arbre/fils gauche et le parcours du sous-arbre/fils droit.

🐍 Script Python

def parcours_infixe(arbre):
    if arbre is None: # cas de l'arbre vide
        return                
    parcours_infixe(arbre.gauche) # on parcourt récursivement le fils gauche
    traitement(arbre.racine) # on traite le noeud racine
    parcours_infixe(arbre.droit) # on parcourt récursivement le fils droit

Pour l'arbre binaire donné en exemple, avec un parcours infixe, l'ordre de traitement des éléments stockés serait :

📋 Texte

O - L - R - A - G - M - T -  E - I - H

Dans le parcours en profondeur suffixe appelé aussi parcours en profondeur postfixe, on taite l'élément stocké dans le noeud après le parcours du sous-arbre/fils gauche et le parcours du sous-arbre/fils droit.

🐍 Script Python

def parcours_postfixe(arbre):
    if arbre is None: # cas de l'arbre vide
        return                
    parcours_postfixe(arbre.gauche) # on parcourt récursivement le fils gauche
    parcours_postfixe(arbre.droit) # on parcourt récursivement le fils droit
    traitement(arbre.racine) # on traite le noeud racine

Pour l'arbre binaire donné en exemple, avec un parcours postfixe, l'ordre de traitement des éléments stockés serait :

📋 Texte

O - R - L - M - E - T - H - I - G - A

Exercice 7 : parcours et mesures

💻 Saisir ses réponses sur Capytale

On rappelle les fonctions de mesure d'arbre binaire taille et hauteur définies dans la section précédente

Fonction	Signature	Description
taille	taille(arbre)	Renvoie le nombre de noeuds dans l'arbre
hauteur	hauteur(arbre)	Renvoie le nombre de noeuds sur le chemin le plus long entre la racine et une feuille de l'arbre

Pour réaliser ces fonctions de mesure il suffit de parcourir l'arbre donc on peut les implémenter avec un parcours en profondeur.

On considère qu'un arbre binaire non vide est implémenté par un objet de la classe Noeud et qu'un arbre vide est représenté par None.

🐍 Script Python

class Noeud:
    """Noeud pour arbre binaire"""
    
    def __init__(self, g, e, d):
        self.gauche = g # lien vers fils gauche g éventuellement vide (None)
        self.element = e # élément e stocké dans le noeud
        self.droit = d # lien vers fils droit d éventuellement vide (None)

Question 1

énoncésolution

Implémentez la fonction taille de façon récursive.

🐍 Script Python

def taille(arbre):
    """Renvoie la taille de l'arbre a"""
    if arbre is None:
        return 0
    return 1 + taille(arbre.gauche) + taille(arbre.droit)

Question 2

énoncésolution

Implémentez la fonction hauteur de façon récursive.

🐍 Script Python

def hauteur(arbre):
    """Renvoie la hauteur de l'arbre"""
    if arbre is None:
        return 0
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

Question 3

énoncésolution

Implémentez une fonction somme(arbre) de façon récursive qui renvoie la somme de tous les éléments contenus dans les noeuds de l'arbre passé en paramètre. Pour simplifier on va considérer que la somme des éléments de l'arbre vide est nulle.

🐍 Script Python

def somme(arbre):
    """Renvoie la somme des valeurs entières stockées dans les noeuds de l'arbre a"""
    if arbre is None:
        return 0
    return arbre.element + somme(arbre.gauche) + somme(arbre.droit)

Exercice 8 : arbre de calcul

💻 Saisir ses réponses sur Capytale

On considère l'arbre binaire représentant l'expression arithmétique \(((3\times(4 - 5)) + (5 \times (12 + 7)))\) :

Question 1

énoncésolution

Dans la console ci-dessous, on donne une implémentation de cet arbre binaire en Python et on lui applique une fonction de parcours en profondeur infixe qui capture dans un tableau dynamique Python trace l'ordre de traitement des noeuds.

• Exécutez la console et constatez que l'écriture de la trace ne correspond pas au calcul représenté par l'arbre selon les règles de priorité des opérations arithmétiques.
• Complétez la fonction parcours_infixe pour qu'elle capture dans trace des parenthèses permettant d'obtenir une écriture conforme au calcul.

🐍 Script Python

def parcours_infixe_parenthese(arbre, trace):
    if arbre is None:
        return 
    trace.append('(')
    parcours_infixe_parenthese(arbre.gauche, trace)
    trace.append(str(arbre.element))
    parcours_infixe_parenthese(arbre.droit, trace)
    trace.append(')')

Question 2

énoncésolution

1. Donnez l'ordre de traitement des éléments de l'arbre par un parcours en profondeur préfixe. Écrire dans la console une fonction parcours_prefixe qui capture dans un tableau dynamique Python trace l'ordre de traitement des noeuds avec un parcours préfixe.
2. Même question pour un parcours postfixe.

Pour un parcours préfixe l'ordre de traitement des éléments contenus dans l'arbre est :

📋 Texte

+ * 3 - 4 5 * 5 + 12 7

Pour un parcours postfixe l'ordre de traitement des éléments contenus dans l'arbre est :

📋 Texte

3 4 5 - * 5 12 7 + * +

Implémentations des parcours :

🐍 Script Python

def parcours_prefixe(arbre, trace):
    if arbre is None:
        return 
    trace.append(str(arbre.element))
    parcours_prefixe(arbre.gauche, trace)    
    parcours_prefixe(arbre.droit, trace)


def parcours_postfixe(arbre, trace):
    if arbre is None:
        return 
    parcours_postfixe(arbre.gauche, trace)    
    parcours_postfixe(arbre.droit, trace)
    trace.append(str(arbre.element))

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Noeud:bksl-nl """Noeud pour arbre binaire"""bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self, g, e, d):bksl-nl self.gauche = g # lien vers fils gauche g éventuellement vide (None)bksl-nl self.element = e # élément e stocké dans le noeudbksl-nl self.droit = d # lien vers fils droit d éventuellement vide (None)bksl-nl bksl-nldef parcourspy-undinfixe(arbre, trace):bksl-nl if arbre is None:bksl-nl return bksl-nl parcourspy-undinfixe(arbre.gauche, trace)bksl-nl trace.append(str(arbre.element))bksl-nl parcourspy-undinfixe(arbre.droit, trace)bksl-nl bksl-nltracepy-undinfixe = []bksl-nlarbrepy-undcalcul = a = Noeud(Noeud(Noeud(None, 3, None), 'py-str', Noeud(Noeud(None, 4, None), '-', Noeud(None, 5, None))), bksl-nl '+', Noeud(Noeud(None, 5, None), 'py-str', Noeud(Noeud(None, 12, None), '+', Noeud(None, 7, None))))bksl-nlparcourspy-undinfixe(arbrepy-undcalcul, tracepy-undinfixe)bksl-nlprint(' '.join(tracepy-undinfixe))bksl-nl

Parcours en largeur d'un arbre binaire

Point de cours 11

Le parcours en largeur d'un arbre binaire visite les noeuds selon leur ordre de profondeur par rapport à la racine : en partant de la racine on épuise d'abord tous les noeuds d'un même niveau avant de passer au niveau suivant. On visite donc d'abord les frères ou cousins d'un noeud avant de passer à ses descendants. En général on explore un niveau de "gauche à droite".

L'acronyme anglais pour désigner le parcours en largeur est BFS pour Breadth First Search.

Exemple de parcours en largeur d'un arbre binaire

Dans le parcours en largeur, on ne passe qu'une seule fois par un noeud donc on traite l'élément stocké dans le noeud dès qu'on le visite. Ainsi l'ordre de traitement par le parcours en largeur des éléments stockés dans l'arbre binaire ci-dessus sera :

📋 Texte

A - L - G - O - R - I - T - H - M - E

Implémentation du parcours en largeur

Pour l'implémentation, on n'utilise pas la récursivité car le parcours en largeur n'explore pas d'abord les fils/sous-arbres. On va utiliser une file (structure FIFO) pour stocker les noeuds en attente ce qui permet de les traiter par profondeur/distance croissante par rapport à la racine.

On commence par enfiler l'arbre (s'il est non vide), puis tant que la file n'est pas vide :

• on défile l'arbre en tête de file ;
• on traite l'élément stocké dans le noeud racine puis on enfile les fils/sous-arbres (gauche puis droite) s'ils existent.

🐍 Script Python

def parcours_largeur(arbre):
    f = creer_file()
    if arbre is not None:
        enfiler(f, arbre)
    while not file_vide(f):
        a = defiler(f)
        traitement(a.racine)
        if a.gauche is not None:
            enfiler(f, a.gauche)
        if a.droit is not None:
            enfiler(f, a.droit)

Exercice 9

💻 Saisir ses réponses sur Capytale

On considère l'arbre binaire ci-dessous :

Question 1

énoncésolution

Énumérez l'ordre de traitement des éléments contenus dans les noeuds par un algorithme de parcours en largeur.

📋 Texte

B R E A D T H

Traduction : LARGEUR

Question 2

énoncésolution

On donne une classe File implémentée avec une deque.

Complétez le code de la fonction parcours_largeur.

###

Lancer Télécharger Téléverser Recharger Sauvegarder

from collections import dequebksl-nlbksl-nlclass Noeud2:bksl-nl """bksl-nl Noeud pour arbre binairebksl-nlbksl-nl On redéfinit une classe Noeud2 pour ne pas avoir de conflitbksl-nl avec la classe Noeud de l'exercice 8 bksl-nl """bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self, g, e, d):bksl-nl self.gauche = g # lien vers fils gauche g éventuellement vide (None)bksl-nl self.element = e # élément e stocké dans le noeudbksl-nl self.droit = d # lien vers fils droit d éventuellement vide (None)bksl-nl bksl-nlbksl-nlclass File:bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.contenu = deque([])bksl-nl bksl-nl def filepy-undvide(self):bksl-nl return len(self.contenu) == 0bksl-nlbksl-nl def defiler(self):bksl-nl assert not self.filepy-undvide(), "File Vide"bksl-nl return self.contenu.popleft()bksl-nl bksl-nl def enfiler(self, elt):bksl-nl self.contenu.append(elt)bksl-nl bksl-nldef parcourspy-undlargeur(arbre):bksl-nl # à compléterbksl-nl ...bksl-nl bksl-nl bksl-nl# construction de l'arbre binairebksl-nla = Noeud2(Noeud2(None, 'R', Noeud2(None, 'A', None)), 'B', Noeud2(Noeud2(None, 'D', None), 'E', Noeud2(Noeud2(None, 'H', None), 'T', None)))bksl-nl# à vous de tester votre fonction parcourspy-undlargeurbksl-nl

🐍 Script Python

from collections import deque

class File:
    
    def __init__(self):
        self.contenu = deque([])
        
    def file_vide(self):
        return len(self.contenu) == 0

    def defiler(self):
        assert not self.file_vide(), "File Vide"
        return self.contenu.popleft()
    
    def enfiler(self, elt):
        self.contenu.append(elt)


class Noeud2:
    """
    Noeud pour arbre binaire

    On redéfinit une classe Noeud2 pour ne pas avoir de conflit
    avec la classe Noeud de l'exercice 8    
    """
    
    def __init__(self, g, e, d):
        self.gauche = g # lien vers fils gauche g éventuellement vide (None)
        self.element = e # élément e stocké dans le noeud
        self.droit = d # lien vers fils droit d éventuellement vide (None)


def parcours_largeur(arbre):
    f = File()
    if arbre is not None:
        f.enfiler(arbre)
    while not f.file_vide():
        a = f.defiler()
        print(a.element)
        if a.gauche is not None:
            f.enfiler(a.gauche)
        if a.droit is not None:
            f.enfiler(a.droit)
        
# construction de l'arbre binaire
a = Noeud2(Noeud2(None, 'R', Noeud2(None, 'A', None)), 'B', Noeud2(Noeud2(None, 'D', None), 'E', Noeud2(Noeud2(None, 'H', None), 'T', None)))