Aller au contenu

🌳 Fiche d'exercice : Les Arbres

⚠️ Attention

Tous les exercices doivent être implémentés en respectant les structures de données d'arbres binaires. 

   class Noeud:
       def __init__(self, valeur):
           self.valeur = valeur
           self.gauche = None
           self.droite = None

À connaître 🦊

🌳 Parcours Préfixe (Préordre)

Ordre de visite : Racine → Sous-arbre gauche → Sous-arbre droite
Utilisation : Copie d'arbre, évaluation d'expressions préfixées
Exemple d'implémentation : 
def parcours_prefixe(noeud):
    if noeud is not None:
        print(noeud.valeur)  # Traiter la racine
        parcours_prefixe(noeud.gauche)  # Parcourir à gauche
        parcours_prefixe(noeud.droite)  # Parcourir à droite
À connaître 🦊

🌳 Parcours Infixe (Inordre)

Ordre de visite : Sous-arbre gauche → Racine → Sous-arbre droite
Utilisation : Affichage trié des ABR, conversion d'expressions
Exemple d'implémentation : 
def parcours_infixe(noeud):
    if noeud is not None:
        parcours_infixe(noeud.gauche)  # Parcourir à gauche
        print(noeud.valeur)  # Traiter la racine
        parcours_infixe(noeud.droite)  # Parcourir à droite
À connaître 🦊

🌳 Parcours Postfixe (Postordre)

Ordre de visite : Sous-arbre gauche → Sous-arbre droite → Racine
Utilisation : Suppression d'arbre, évaluation d'expressions postfixées
Exemple d'implémentation : 
def parcours_postfixe(noeud):
    if noeud is not None:
        parcours_postfixe(noeud.gauche)  # Parcourir à gauche
        parcours_postfixe(noeud.droite)  # Parcourir à droite
        print(noeud.valeur)  # Traiter la racine
À connaître 🦊

🔍 Insertion dans un ABR

Principe : Comparer la valeur avec la racine et insérer récursivement
Complexité : O(log n) en moyenne, O(n) dans le pire cas
Exemple d'implémentation : 
def inserer(racine, valeur):
    if racine is None:
        return Noeud(valeur)
    if valeur < racine.valeur:
        racine.gauche = inserer(racine.gauche, valeur)
    else:
        racine.droite = inserer(racine.droite, valeur)
    return racine
À connaître 🦊

🗑️ Suppression dans un ABR

3 cas à gérer :
• Cas 1 : Nœud feuille → Suppression directe
• Cas 2 : Nœud avec un enfant → Remplacer par l'enfant
• Cas 3 : Nœud avec deux enfants → Remplacer par le successeur
Le successeur est le plus petit élément du sous-arbre droit
Introduction 🦊

Exercice 1 - Création d'un arbre simple

Créer un arbre binaire avec une racine de valeur 10, un enfant gauche de valeur 5 et un enfant droit de valeur 15.
Afficher les valeurs des trois nœuds. 
class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droite = None

# Création de l'arbre
racine = Noeud(10)
racine.gauche = Noeud(5)
racine.droite = Noeud(15)

# Affichage
print(f"Racine: {racine.valeur}")
print(f"Enfant gauche: {racine.gauche.valeur}")
print(f"Enfant droit: {racine.droite.valeur}")
Introduction 🦊

Exercice 2 - Parcours préfixe simple

Implémenter une fonction de parcours préfixe qui affiche les valeurs des nœuds.
Tester avec l'arbre créé dans l'exercice 1. 
def parcours_prefixe(noeud):
    if noeud is not None:
        print(noeud.valeur)
        parcours_prefixe(noeud.gauche)
        parcours_prefixe(noeud.droite)

# Test avec l'arbre précédent
parcours_prefixe(racine)
# Affiche: 10, 5, 15
Introduction 🦊

Exercice 3 - Insertion simple dans un ABR

Créer un ABR vide et y insérer les valeurs 8, 3, 10, 1, 6, 14, 4, 7, 13.
Afficher l'arbre avec un parcours infixe pour vérifier l'ordre. 
def inserer(racine, valeur):
    if racine is None:
        return Noeud(valeur)
    if valeur < racine.valeur:
        racine.gauche = inserer(racine.gauche, valeur)
    else:
        racine.droite = inserer(racine.droite, valeur)
    return racine

def parcours_infixe(noeud):
    if noeud is not None:
        parcours_infixe(noeud.gauche)
        print(noeud.valeur, end=" ")
        parcours_infixe(noeud.droite)

# Création de l'ABR
abr = None
valeurs = [8, 3, 10, 1, 6, 14, 4, 7, 13]
for val in valeurs:
    abr = inserer(abr, val)

# Affichage trié
parcours_infixe(abr)
# Affiche: 1 3 4 6 7 8 10 13 14
Facile 🦊

Exercice 4 - Calcul de la hauteur

Écrire une fonction qui calcule la hauteur d'un arbre binaire.
La hauteur d'un arbre vide est -1, celle d'une feuille est 0. 
def hauteur(noeud):
    if noeud is None:
        return -1
    hauteur_gauche = hauteur(noeud.gauche)
    hauteur_droite = hauteur(noeud.droite)
    return 1 + max(hauteur_gauche, hauteur_droite)
Facile 🦊

Exercice 5 - Recherche dans un ABR

Écrire une fonction qui recherche une valeur dans un ABR et renvoie True si elle existe, False sinon. 
def rechercher(racine, valeur):
    if racine is None:
        return False
    if racine.valeur == valeur:
        return True
    elif valeur < racine.valeur:
        return rechercher(racine.gauche, valeur)
    else:
        return rechercher(racine.droite, valeur)
Facile 🦊

Exercice 6 - Compter les nœuds

Écrire une fonction qui compte le nombre total de nœuds dans un arbre binaire. 
def compter_noeuds(noeud):
    if noeud is None:
        return 0
    return 1 + compter_noeuds(noeud.gauche) + compter_noeuds(noeud.droite)
Intermédiaire 🦊🦊

Exercice 7 - Suppression d'une feuille

Implémenter la suppression d'un nœud feuille dans un ABR.
Gérer uniquement le cas où le nœud à supprimer est une feuille. 
def supprimer_feuille(racine, valeur):
    if racine is None:
        return None

    if valeur < racine.valeur:
        racine.gauche = supprimer_feuille(racine.gauche, valeur)
    elif valeur > racine.valeur:
        racine.droite = supprimer_feuille(racine.droite, valeur)
    else:
        # Nœud trouvé
        if racine.gauche is None and racine.droite is None:
            # C'est une feuille
            return None
        else:
            print(f"Le nœud {valeur} n'est pas une feuille")

    return racine
Intermédiaire 🦊🦊

Exercice 8 - Parcours en largeur

Implémenter un parcours en largeur (niveau par niveau) d'un arbre binaire.
Utiliser une file (queue) pour l'implémentation. 
from collections import deque

def parcours_largeur(racine):
    if racine is None:
        return

    file = deque([racine])

    while file:
        noeud = file.popleft()
        print(noeud.valeur, end=" ")

        if noeud.gauche:
            file.append(noeud.gauche)
        if noeud.droite:
            file.append(noeud.droite)
Intermédiaire 🦊🦊

Exercice 9 - Minimum et Maximum d'un ABR

Écrire deux fonctions pour trouver la valeur minimale et maximale dans un ABR. 
def minimum_abr(racine):
    if racine is None:
        return None
    while racine.gauche is not None:
        racine = racine.gauche
    return racine.valeur

def maximum_abr(racine):
    if racine is None:
        return None
    while racine.droite is not None:
        racine = racine.droite
    return racine.valeur
Difficile 🦊🦊🦊

Exercice 10 - Suppression complète dans un ABR

Implémenter la suppression complète d'un nœud dans un ABR (gérer les 3 cas).
Cas 1: feuille, Cas 2: un enfant, Cas 3: deux enfants 
def supprimer(racine, valeur):
    if racine is None:
        return None

    if valeur < racine.valeur:
        racine.gauche = supprimer(racine.gauche, valeur)
    elif valeur > racine.valeur:
        racine.droite = supprimer(racine.droite, valeur)
    else:
        # Nœud trouvé
        # Cas 1: Nœud feuille
        if racine.gauche is None and racine.droite is None:
            return None

        # Cas 2: Nœud avec un seul enfant
        elif racine.gauche is None:
            return racine.droite
        elif racine.droite is None:
            return racine.gauche

        # Cas 3: Nœud avec deux enfants
        else:
            # Trouver le successeur (minimum du sous-arbre droit)
            successeur = racine.droite
            while successeur.gauche is not None:
                successeur = successeur.gauche

            # Remplacer la valeur
            racine.valeur = successeur.valeur

            # Supprimer le successeur
            racine.droite = supprimer(racine.droite, successeur.valeur)

    return racine
Difficile 🦊🦊🦊

Exercice 11 - Vérifier si un arbre est un ABR

Écrire une fonction qui vérifie si un arbre binaire donné respecte les propriétés d'un ABR. 
def est_abr(racine, min_val=float('-inf'), max_val=float('inf')):
    if racine is None:
        return True

    if racine.valeur <= min_val or racine.valeur >= max_val:
        return False

    return (est_abr(racine.gauche, min_val, racine.valeur) and
            est_abr(racine.droite, racine.valeur, max_val))
Difficile 🦊🦊🦊

Exercice 12 - Reconstruction d'un ABR

À partir d'un parcours infixe et préfixe, reconstruire l'ABR original.
Exemple: Infixe [1,3,4,6,7,8,10,13,14], Préfixe [8,3,1,6,4,7,10,14,13] 
def reconstruire_abr(prefixe, infixe):
    if not prefixe or not infixe:
        return None

    # La racine est le premier élément du parcours préfixe
    racine_val = prefixe[0]
    racine = Noeud(racine_val)

    # Trouver la position de la racine dans le parcours infixe
    idx_racine = infixe.index(racine_val)

    # Diviser les parcours
    infixe_gauche = infixe[:idx_racine]
    infixe_droite = infixe[idx_racine + 1:]

    prefixe_gauche = prefixe[1:1 + len(infixe_gauche)]
    prefixe_droite = prefixe[1 + len(infixe_gauche):]

    # Construire récursivement les sous-arbres
    racine.gauche = reconstruire_abr(prefixe_gauche, infixe_gauche)
    racine.droite = reconstruire_abr(prefixe_droite, infixe_droite)

    return racine