Chapitre 5 - Révision : Les arbres

---

1. Arbres binaires

• Arbre binaire : vide ou nœud + sous-arbre gauche + sous-arbre droit
• Racine : nœud au sommet | Feuille : nœud sans enfant
• Taille : 1 + taille(g) + taille(d) | arbre vide → 0
• Hauteur : 1 + max(hauteur(g), hauteur(d)) | arbre vide → -1
• Encadrement : $\lfloor \log_2 n \rfloor \leq h \leq n - 1$

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

---

2. Arbres binaires

• Arbre binaire : structure récursive (vide ou nœud + gauche + droit)
• Taille : 1 + taille(gauche) + taille(droit), arbre vide → 0
• Hauteur : 1 + max(hauteur(gauche), hauteur(droit)), arbre vide → -1
• Encadrement : $\lfloor \log_2 n \rfloor \leq h \leq n-1$

Parcours	Ordre	Structure
Préfixe	Racine → Gauche → Droit	Récursion
Infixe	Gauche → Racine → Droit	Récursion
Suffixe	Gauche → Droit → Racine	Récursion
Largeur	Niveau par niveau	File (FIFO)

ABR : gauche < racine < droit. Infixe = ordre croissant. Recherche O(log₂ n) si équilibré.