Arbres et arbres binaires : représenter une hiérarchie

Un cap pour ce chapitre

Ce que vous saurez faire

Identifier racine, nœuds, feuilles et sous-arbres.
Distinguer arbre général et arbre binaire.
Calculer taille et hauteur selon une convention explicite.

Les bases utiles pour commencer

Structures de données : interface et implémentation

Une racine et des descendants

Un arbre enraciné organise des nœuds à partir d’une racine. Chaque nœud autre que la racine possède un parent unique. Les liens conduisent vers des enfants ; une feuille est un nœud sans enfant. Les descendants d’un nœud, avec ce nœud lui-même, forment un sous-arbre.

Une même notion peut être représentée par un graphe dans un autre contexte, mais un arbre impose une hiérarchie particulière. Si un élément possède deux parents ou qu’un lien ramène à un ancêtre, la représentation ne correspond plus à l’arbre enraciné simple étudié ici. Le chemin depuis la racine vers un nœud est unique.

Un arbre représente une relation hiérarchique déterminée : « contient directement », « est une sous-partie de » ou « résulte de cette décision ». Cette relation doit rester la même sur tout le schéma. Un dossier partagé par deux parents ne correspond pas à l’arbre simple annoncé. Le modèle peut alors nécessiter un graphe ou une duplication explicitement choisie, selon la question.

Deux positions d’enfants bien distinguées

Dans un arbre binaire, chaque nœud dispose au plus d’un enfant gauche et d’un enfant droit. Les deux positions ont un sens : un nœud avec seulement un enfant gauche n’a pas la même structure qu’un nœud avec seulement un enfant droit. « Binaire » ne signifie pas que chaque nœud possède exactement deux enfants.

On peut représenter un arbre binaire par des objets contenant valeur, gauche et droite, ou par une structure récursive utilisant des tuples. L’absence de sous-arbre doit être codée sans ambiguïté, par exemple avec None. La représentation choisie détermine ensuite la façon d’écrire les parcours et les calculs.

Mesurer sans confondre taille et hauteur

La taille est le nombre de nœuds. La hauteur mesure le plus long chemin de la racine à une feuille. Dans cette page, elle compte les arêtes : une racine seule a hauteur 0 et un arbre vide hauteur -1 par convention de calcul. Certains cours comptent les nœuds du chemin : toutes les hauteurs non vides sont alors augmentées de 1.

Annoncez la convention avant de comparer deux réponses. Pour un arbre de racine A avec deux feuilles B et C, la taille vaut 3 et la hauteur en arêtes vaut 1. Le nombre de feuilles vaut 2 : aucune de ces quantités ne doit être utilisée à la place des autres.

La profondeur d’un nœud est sa distance depuis la racine en nombre d’arêtes. La hauteur de l’arbre est la plus grande profondeur rencontrée. Une feuille peut se trouver à une profondeur inférieure à cette hauteur : elle se définit par l’absence d’enfant, pas par sa position sur le dernier niveau dessiné.

Encadrer la hauteur et comprendre la forme

Pour n nœuds non vides, la plus grande hauteur possible est n - 1 : tous les nœuds sont en chaîne. À hauteur h, un arbre binaire contient au plus 1 + 2 + … + 2^h = 2^(h+1) - 1 nœuds. Cela donne une borne inférieure sur la hauteur : plafond(log₂(n + 1)) - 1.

Un arbre rempli niveau par niveau atteint cette petite hauteur ; une chaîne atteint la plus grande. Ces formes n’ont pas les mêmes conséquences sur les parcours de recherche. L’atelier compare les extrêmes sans assimiler tous les arbres binaires à des arbres de recherche : l’ordre des valeurs est une propriété supplémentaire.

Exemple suivi : calculer de bas en haut

A possède B à gauche et C à droite ; B possède D à droite ; C possède E à gauche et F à droite. Les feuilles D,E,F ont chacune taille 1 et hauteur 0. B a taille 2 et hauteur 1 ; C a taille 3 et hauteur 1. A a donc taille 1+2+3=6 et hauteur 1+max(1,1)=2.

Ces calculs utilisent deux relations : taille d’un arbre non vide = 1 plus les tailles de ses sous-arbres, hauteur = 1 plus la plus grande des hauteurs des sous-arbres. L’arbre vide a taille 0 et hauteur -1 dans notre convention, ce qui rend la formule correcte pour une feuille. Il n’est pas nécessaire de confondre les deux opérations : les tailles s’additionnent, tandis que seule la branche la plus profonde détermine la hauteur.

Utiliser les bornes pour contrôler un dessin

À hauteur 2, un arbre binaire contient au plus 1+2+4=7 nœuds. Un dessin annonçant huit nœuds et hauteur 2 est donc impossible. À hauteur 3, il peut contenir de 4 nœuds en chaîne jusqu’à 15 si tous les niveaux sont remplis. La même hauteur n’impose donc ni une taille précise ni un nombre précis de feuilles.

Pour huit nœuds, la hauteur minimale est 3 et la maximale 7. Un arbre rempli niveau par niveau atteint la première ; une chaîne atteint la seconde. Ce contraste montre pourquoi connaître seulement le nombre de données ne suffit pas à prévoir la longueur des chemins. Enfin, les valeurs peuvent apparaître dans n’importe quel ordre dans un arbre binaire général. Les règles de comparaison d’un arbre binaire de recherche constituent des contraintes supplémentaires étudiées séparément.

À vous de faire varier les choses

Même taille, autre silhouette

Faites varier le nombre de nœuds et passez d’un remplissage par niveaux à une chaîne. La hauteur est comptée en arêtes.

Lire le résultat de l’expérience initiale

Taille 7, hauteur 2 arête(s).

Les numéros identifient les nœuds ; ils ne définissent pas un arbre de recherche. L’arbre vide a hauteur -1 dans cette convention.

Nœud	Profondeur	Gauche	Droite
0	0	1	2
1	1	3	4
2	1	5	6
3	2	vide	vide
4	2	vide	vide
5	2	vide	vide
6	2	vide	vide

Indice 2

Binaire autorise un seul enfant.

Comprendre la correction

Les deux arbres ont taille 2 et hauteur 1. Ils sont tous deux binaires, mais leurs structures diffèrent car l’emplacement de l’enfant change. Les mesures numériques ne suffisent donc pas à identifier toute la structure. Aucune règle de recherche sur les valeurs n’était imposée.

Les erreurs qui méritent un détour

Compter uniquement les feuilles pour obtenir la taille.: La taille inclut tous les nœuds, racine et nœuds internes compris.
Oublier de préciser la convention de hauteur.: Compter les arêtes ou les nœuds produit un décalage de 1. Lisez la définition donnée dans l’exercice.

La fiche à garder

L’essentiel à retenir

Un arbre binaire distingue sous-arbres gauche et droit.
Taille, nombre de feuilles et hauteur sont des mesures différentes.
La forme détermine la hauteur pour une taille fixée.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

Le prochain pas

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.