Séance 1 — Vocabulaire et implémentation

1. Qu'est-ce qu'un arbre binaire ?

Un arbre binaire est une structure hiérarchique où chaque nœud a au maximum deux enfants (fils gauche et fils droit).

2. Exercice 1 — Lecture de vocabulaire

3. Les arbres sont des structures récursives

Un arbre binaire est soit vide, soit un nœud racine avec deux sous-arbres (éventuellement vides), eux-mêmes des arbres binaires. C'est la base de la récursivité.

4. Formes extrêmes et encadrement

Filiforme (dégénéré) : chaque nœud n'a qu'un seul fils, hauteur = n. Complet/parfait : tous les niveaux remplis, hauteur ≈ log₂(n). Pour tout arbre : log₂(n) ≤ h ≤ n - 1.

5. Exercice 2 — Encadrement taille/hauteur

6. Exercice 3 — Implémentation avec la classe Noeud

class Noeud:
    def __init__(self, e, g=None, d=None):
        self.etiquette = e
        self.gauche = g
        self.droit = d

    def est_feuille(self):
        return self.gauche is None and self.droit is None

A1 = Noeud(2, Noeud(8, Noeud(4), Noeud(5)), Noeud(9, None, Noeud(3)))
print(A1)   # 2-(8-(4,5),9-(None,3))
print(A1.gauche.gauche.est_feuille())   # True

7. Exercice 4 — hauteur() et taille() récursives

def taille(A):
    if A is None:
        return 0
    return 1 + taille(A.gauche) + taille(A.droit)

def hauteur(A):
    if A is None:
        return -1
    return 1 + max(hauteur(A.gauche), hauteur(A.droit))

Exercices défis (bonus)

def parfait(h):
    if h == 0:
        return None
    return Noeud(f'Niveau{h}', parfait(h-1), parfait(h-1))

def peigne_gauche(h):
    if h == 0:
        return None
    return Noeud(f'Niveau{h}', peigne_gauche(h-1), None)