Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
Un arbre binaire est un arbre où chaque nœud possède au plus deux enfants : un sous-arbre gauche et un sous-arbre droit, chacun pouvant être vide. L'ordre gauche/droite est significatif (deux arbres avec gauche et droit échangés sont différents).
Vocabulaire : racine, feuille (gauche et droit vides), nœud interne, et les deux sous-arbres pour chaque nœud.
_Figure : un arbre binaire de hauteur 2 avec sa racine R, ses nœuds internes, ses feuilles et ses deux sous-arbres._
Un arbre binaire est parfait (complet) quand tous les niveaux sont entièrement remplis. Sa hauteur conditionne fortement l'efficacité des algorithmes : un arbre équilibré a une hauteur de l'ordre de \log_2 n, alors qu'un arbre filiforme (dégénéré en liste) a une hauteur n-1, ce qui ruine la performance des recherches.
Pour un arbre binaire de hauteur h (racine seule : h=0) : \text{nœuds} \le 2^{h+1} - 1, \qquad \text{feuilles} \le 2^{h}.
Pour n nœuds, la hauteur vérifie : \lfloor \log_2 n \rfloor \le h \le n - 1.
Représentation et calcul de hauteur :
class Noeud: def __init__(self, valeur, gauche=None, droit=None): self.valeur = valeur self.gauche = gauche self.droit = droit
def hauteur(a): if a is None: return -1 return 1 + max(hauteur(a.gauche), hauteur(a.droit))
1. Dessiner l'arbre niveau par niveau pour visualiser gauche/droite.
2. Pour un calcul (hauteur, taille, somme), écrire une fonction récursive : cas de base = arbre vide (None), cas récursif = combiner gauche et droit.
3. Utiliser 2^{h+1}-1 pour relier hauteur et nombre de nœuds.
4. Penser au pire cas (arbre filiforme) pour la complexité.
None (arbre vide) dans une fonction récursive : provoque une AttributeError.Les fonctions récursives sur arbres binaires (hauteur, taille, somme des valeurs, recherche d'un élément, nombre de feuilles) sont au cœur de l'épreuve. Structurez systématiquement en cas de base None + récursion sur a.gauche et a.droit, puis combinez les deux résultats (somme, maximum, etc.). Sachez justifier qu'un arbre équilibré donne des recherches en O(\log n) alors qu'un arbre filiforme tombe à O(n). La représentation par classe Noeud (avec valeur, gauche, droit et l'arbre vide codé par None) est la convention attendue : un sujet peut aussi proposer une représentation par tuples imbriqués, dont il faut alors adapter le code récursif.