Arbres : structures hiérarchiques

Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

L'essentiel

Un arbre est une structure de données hiérarchique : les nœuds sont organisés en niveaux. Il possède un nœud racine unique ; chaque autre nœud a exactement un parent et peut avoir plusieurs enfants. Il n'y a pas de cycle.

Vocabulaire essentiel : - Racine : l'unique nœud sans parent. - Feuille : un nœud sans enfant. - Nœud interne : un nœud ayant au moins un enfant. - Sous-arbre : un nœud avec l'ensemble de ses descendants. - Parent / enfant : relation directe entre deux nœuds reliés.

Deux grandeurs importantes : - La profondeur d'un nœud est le nombre d'arêtes depuis la racine (racine de profondeur 0). - La hauteur de l'arbre est la profondeur maximale, soit la longueur du plus long chemin racine-feuille. - La taille est le nombre total de nœuds.

Formules et schémas clés

Propriété fondamentale : un arbre à n nœuds a exactement n - 1 \text{ arêtes.}

Représentation par dictionnaire d'enfants (listes d'adjacence) :

enfants = {'A': ['B', 'C'], 'B': ['D'], 'C': [], 'D': []} # A est la racine ; C et D sont des feuilles

Parcours récursif type (comptage de feuilles) :

def nb_feuilles(enfants, n): if enfants[n] == []: # cas de base : feuille return 1 return sum(nb_feuilles(enfants, f) for f in enfants[n])

Méthode type bac

1. Identifier la racine, puis distinguer feuilles et nœuds internes. 2. Pour la hauteur, suivre le plus long chemin racine-feuille. 3. Sur un arbre représenté par dictionnaire, raisonner récursivement : cas de base (feuille) puis somme/maximum sur les enfants. 4. Vérifier les conventions de l'énoncé (profondeur/hauteur comptées en arêtes ou en nœuds).

Pièges

  • Confondre hauteur (longueur d'un chemin) et taille (nombre de nœuds).
  • Attention à la convention de hauteur : certains comptent les nœuds, d'autres les arêtes ; un arbre à un seul nœud a une hauteur 0 (arêtes) ou 1 (nœuds).
  • Un arbre n'a pas de cycle et chaque nœud (sauf racine) a un parent unique : sinon c'est un graphe.
  • Une feuille est un nœud sans enfant, ce n'est pas forcément le nœud le plus profond.

Pour l'épreuve

Les arbres servent à modéliser des données hiérarchiques (fichiers, HTML, classifications). Le correcteur attend une maîtrise du vocabulaire et de la propriété n-1 arêtes. Les fonctions récursives de comptage (feuilles, nœuds, hauteur) sont des classiques : structurez-les en cas de base + cas récursif. C'est le socle indispensable avant d'aborder les arbres binaires.