Exercices : arbres binaires

B. La hauteur est la profondeur maximale des feuilles. La racine seule est une feuille de profondeur 0, donc la hauteur est 0. La valeur \(-1\) (A) correspond à un arbre vide (sans aucun nœud). L’erreur C confond hauteur et taille (l’arbre a un seul nœud, donc taille 1).

D. Un arbre binaire complet de hauteur \(h\) contient au maximum \(2^{h+1} - 1\) nœuds. Pour \(h = 3\) : \(2^4 - 1 = 15\). L’erreur B correspond à \(h = 2\) (\(2^3 - 1 = 7\)). L’erreur C confond avec \(2^h\).

B. Le parcours infixe visite d’abord le sous-arbre gauche (valeurs plus petites), puis la racine, puis le sous-arbre droit (valeurs plus grandes). Dans un ABR, cela produit les valeurs dans l’ordre croissant. Le préfixe (A) commence par la racine. Le suffixe (C) termine par la racine. Le parcours en largeur (D) visite niveau par niveau, sans respecter l’ordre des valeurs.

A. Dans un ABR équilibré, la recherche est en \(O(\log_2 n)\). Or \(\log_2(1,000) \approx 10\). On compare au maximum une fois par niveau, soit environ 10 comparaisons. L’erreur C (500) ou D (1 000) correspondent à un parcours séquentiel. L’erreur B (42) confond la valeur cherchée avec le nombre de comparaisons.

B. Chaque valeur insérée est plus grande que toutes les précédentes, donc elle est systématiquement placée à droite. On obtient un arbre peigne : 1 → (droit) 2 → (droit) 3 → (droit) 4 → (droit) 5, de hauteur 4. C’est le pire cas pour un ABR : la recherche y est en \(O(n)\).

Méthode : pour le préfixe, on traite la racine R d’abord, puis on descend récursivement à gauche (A, puis C qui est une feuille, puis D, puis F), puis à droite (B, puis E).

Ordre en largeur : R, A, B, C, D, E, F (niveau par niveau).

3. Taille = 7 nœuds. Hauteur = 3 (chemin le plus long : R → A → D → F, soit 3 arêtes).

a)

def contient(arbre, x):
    if arbre is None:
        return False
    if arbre.valeur == x:
        return True
    return contient(arbre.gauche, x) or contient(arbre.droit, x)

Dans un arbre quelconque, on doit explorer les deux sous-arbres car on ne peut pas exclure un côté. Le or garantit qu’on renvoie True dès que l’élément est trouvé dans l’un des sous-arbres.

b)

def liste_feuilles(arbre):
    if arbre is None:
        return []
    if arbre.gauche is None and arbre.droit is None:
        return [arbre.valeur]
    return liste_feuilles(arbre.gauche) + liste_feuilles(arbre.droit)

Une feuille est un nœud sans fils. On renvoie sa valeur dans une liste à un élément. Pour un nœud interne, on concatène les feuilles des deux sous-arbres.

c)

def prefixe_liste(arbre):
    if arbre is None:
        return []
    return [arbre.valeur] + prefixe_liste(arbre.gauche) + prefixe_liste(arbre.droit)

Le parcours préfixe place la racine avant les sous-arbres gauche et droit.

1. Arbre final :

          8
        /   \
       3     10
      / \      \
     1   6     14
        / \    /
       4   7  13

Étapes clés :

• 8 → racine.
• 3 < 8 → fils gauche de 8.
• 10 > 8 → fils droit de 8.
• 1 < 8, 1 < 3 → fils gauche de 3.
• 6 < 8, 6 > 3 → fils droit de 3.
• 14 > 8, 14 > 10 → fils droit de 10.
• 4 < 8, 4 > 3, 4 < 6 → fils gauche de 6.
• 7 < 8, 7 > 3, 7 > 6 → fils droit de 6.
• 13 > 8, 13 > 10, 13 < 14 → fils gauche de 14.

2. Taille = 9 nœuds. Hauteur = 3 (chemin le plus long : 8 → 10 → 14 → 13 ou 8 → 3 → 6 → 4).

3. Parcours infixe : 1, 3, 4, 6, 7, 8, 10, 13, 14. C’est bien l’ordre croissant. ✓

4. Recherche de 7 :

   • Comparer 7 à 8 : 7 < 8 → aller à gauche.
   • Comparer 7 à 3 : 7 > 3 → aller à droite.
   • Comparer 7 à 6 : 7 > 6 → aller à droite.
   • Comparer 7 à 7 : trouvé ! ✓

   Quatre comparaisons, ce qui correspond à la profondeur du nœud 7 (niveau 3) + 1.

def somme(arbre):
    if arbre is None:
        return 0
    return arbre.valeur + somme(arbre.gauche) + somme(arbre.droit)

Cas de base : arbre vide → 0. Récurrence : on ajoute la valeur de la racine aux sommes des sous-arbres.

def miroir(arbre):
    if arbre is None:
        return None
    return Arbre(arbre.valeur, miroir(arbre.droit), miroir(arbre.gauche))

On crée un nouvel arbre où le sous-arbre gauche est le miroir du droit, et inversement. L’arbre original n’est pas modifié.

def meme_structure(a1, a2):
    if a1 is None and a2 is None:
        return True
    if a1 is None or a2 is None:
        return False
    return meme_structure(a1.gauche, a2.gauche) and meme_structure(a1.droit, a2.droit)

Deux arbres ont la même structure si :

• ils sont tous les deux vides, ou
• ils sont tous les deux non vides et leurs sous-arbres gauches ont la même structure et leurs sous-arbres droits aussi.

1. L’expression \((5 + 1) \times 2 - (9 / 3)\) se décompose en \(((5+1) \times 2) - (9 / 3)\) :

          -
         / \
        *   /
       / \ / \
      +  2 9  3
     / \
    5   1

def evaluer(arbre):
    # Cas de base : feuille (nombre)
    if arbre.gauche is None and arbre.droit is None:
        return arbre.valeur

    # Évaluer les sous-arbres
    g = evaluer(arbre.gauche)
    d = evaluer(arbre.droit)

    # Appliquer l'opérateur
    if arbre.valeur == "+":
        return g + d
    elif arbre.valeur == "-":
        return g - d
    elif arbre.valeur == "*":
        return g * d
    elif arbre.valeur == "/":
        return g / d

Vérification : pour le premier arbre, evaluer calcule \((3+4) \times (8-2) = 7 \times 6 = 42\). ✓

Pour l’arbre de la question 1 : \((5+1) \times 2 - 9/3 = 12 - 3 = 9\). ✓

3. La NPI correspond au parcours suffixe (gauche, droit, nœud). Pour le premier arbre : 3 4 + 8 2 - *. Pour l’arbre de la question 1 : 5 1 + 2 * 9 3 / -.

def infixe_parenthesee(arbre):
    if arbre.gauche is None and arbre.droit is None:
        return str(arbre.valeur)
    g = infixe_parenthesee(arbre.gauche)
    d = infixe_parenthesee(arbre.droit)
    return "(" + g + arbre.valeur + d + ")"

Pour le premier arbre : "((3+4)*(8-2))". ✓