🌳 Parcours d'Arbres

🎯 Introduction aux Parcours

🚶 Parcours d'arbre

Un parcours d'arbre est une méthode systématique pour visiter tous les nœuds d'un arbre dans un ordre spécifique. Chaque parcours suit une stratégie différente selon l'ordre de visite des nœuds.

🎯

Objectif

Traiter chaque nœud exactement une fois selon une stratégie définie.

🔄

Récursivité

Les parcours utilisent la nature récursive des arbres pour une implémentation élégante.

⚡

Complexité

Tous les parcours ont une complexité temporelle O(n) car chaque nœud est visité une fois.

🔄 Types de Parcours

1️⃣

Parcours Préfixe

Racine → Gauche → Droite
Visite d'abord la racine, puis le sous-arbre gauche, enfin le sous-arbre droit.

2️⃣

Parcours Infixe

Gauche → Racine → Droite
Visite le sous-arbre gauche, puis la racine, enfin le sous-arbre droit.

3️⃣

Parcours Postfixe

Gauche → Droite → Racine
Visite les sous-arbres gauche et droit avant la racine.

🌟 Applications Pratiques

📋

Parcours Préfixe

Utilisations :

• Copie d'arbres
• Sérialisation
• Évaluation d'expressions préfixées
• Création de structures hiérarchiques

🔢

Parcours Infixe

Utilisations :

• Tri d'arbres binaires de recherche
• Évaluation d'expressions mathématiques
• Affichage ordonné des données
• Validation de propriétés ABR

🧮

Parcours Postfixe

Utilisations :

• Suppression d'arbres
• Calcul de taille/hauteur
• Évaluation d'expressions postfixées
• Libération de mémoire

💻 Implémentations Python

1️⃣ Parcours Préfixe

Traite la racine avant ses enfants - idéal pour la copie et la sérialisation.

💻 Implémentation Préfixe

def parcours_prefixe(self, noeud=None, resultat=None):
    """
    Parcours préfixe : Racine → Gauche → Droite
    Retourne la liste des valeurs dans l'ordre de visite
    """
    if resultat is None:
        resultat = []

    if noeud is None:
        noeud = self.racine

    if noeud is not None:
        # 1. Traiter la racine
        resultat.append(noeud.valeur)

        # 2. Parcourir le sous-arbre gauche
        self.parcours_prefixe(noeud.gauche, resultat)

        # 3. Parcourir le sous-arbre droit
        self.parcours_prefixe(noeud.droite, resultat)

    return resultat

2️⃣ Parcours Infixe

Traite la racine entre ses enfants - produit un ordre trié pour les ABR.

💻 Implémentation Infixe

def parcours_infixe(self, noeud=None, resultat=None):
    """
    Parcours infixe : Gauche → Racine → Droite
    Pour un ABR, produit les valeurs en ordre croissant
    """
    if resultat is None:
        resultat = []

    if noeud is None:
        noeud = self.racine

    if noeud is not None:
        # 1. Parcourir le sous-arbre gauche
        self.parcours_infixe(noeud.gauche, resultat)

        # 2. Traiter la racine
        resultat.append(noeud.valeur)

        # 3. Parcourir le sous-arbre droit
        self.parcours_infixe(noeud.droite, resultat)

    return resultat

3️⃣ Parcours Postfixe

Traite la racine après ses enfants - idéal pour les calculs et la suppression.

💻 Implémentation Postfixe

def parcours_postfixe(self, noeud=None, resultat=None):
    """
    Parcours postfixe : Gauche → Droite → Racine
    Idéal pour calculer des propriétés ou supprimer l'arbre
    """
    if resultat is None:
        resultat = []

    if noeud is None:
        noeud = self.racine

    if noeud is not None:
        # 1. Parcourir le sous-arbre gauche
        self.parcours_postfixe(noeud.gauche, resultat)

        # 2. Parcourir le sous-arbre droit
        self.parcours_postfixe(noeud.droite, resultat)

        # 3. Traiter la racine
        resultat.append(noeud.valeur)

    return resultat

🧪 Exemple Complet

🌳 Arbre d'exemple

       A
      / \
     B   C
    / \   \
   D   E   F

🔄

Résultats des Parcours

Préfixe : A, B, D, E, C, F
Infixe : D, B, E, A, C, F
Postfixe : D, E, B, F, C, A

💻

Code de Test

💻 Test des Parcours

# Construction de l'arbre
racine = NoeudBinaire('A')
racine.gauche = NoeudBinaire('B')
racine.droite = NoeudBinaire('C')
racine.gauche.gauche = NoeudBinaire('D')
racine.gauche.droite = NoeudBinaire('E')
racine.droite.droite = NoeudBinaire('F')

arbre = ArbreBinaire(racine)

# Tests des parcours
print("Préfixe :", arbre.parcours_prefixe())
print("Infixe :", arbre.parcours_infixe())
print("Postfixe :", arbre.parcours_postfixe())

⚡ Analyse de Complexité

📊 Complexité des Parcours

Parcours	Complexité Temporelle	Complexité Spatiale	Remarques
Préfixe	O(n)	O(h)	h = hauteur de l'arbre
Infixe	O(n)	O(h)	Ordre trié pour ABR
Postfixe	O(n)	O(h)	Idéal pour suppression

💡 Important : La complexité spatiale O(h) correspond à la pile d'appels récursifs, où h est la hauteur de l'arbre.

🎯 Points Clés à Retenir

🔄

Récursivité Naturelle

Les parcours exploitent la structure récursive des arbres pour une implémentation élégante et intuitive.

⚡

Efficacité Optimale

Complexité O(n) incontournable car chaque nœud doit être visité exactement une fois.

🎯

Choix Stratégique

Le choix du parcours dépend de l'application : préfixe pour copier, infixe pour trier, postfixe pour calculer.