Calculer la taille et la hauteur d’un arbre

Compter tous les nœuds

La taille d’un arbre vide vaut zéro. Pour un arbre non vide, on compte sa racine, les nœuds du sous-arbre gauche et ceux du sous-arbre droit : taille(A)=1+taille(G)+taille(D). Les sous-arbres ne partagent pas de nœuds dans le modèle arborescent ; cette addition ne compte donc personne deux fois.

Considérons une racine 8, un sous-arbre gauche de racine 3 avec feuilles 1 et 6, et un sous-arbre droit de racine 10 avec une feuille droite 14. Le sous-arbre gauche contient trois nœuds, le droit deux ; l’arbre entier contient six nœuds. Les étiquettes numériques ne servent pas au calcul de taille.

Choisir ce que signifie hauteur

Nous comptons ici la hauteur en nombre d’arêtes sur le plus long chemin entre la racine et une feuille. Une feuille a donc hauteur zéro et nous attribuons à l’arbre vide la hauteur -1. Pour un arbre non vide, hauteur(A)=1+max(hauteur(G),hauteur(D)). La valeur -1 permet à la formule de fonctionner pour une feuille.

Une autre convention compte les niveaux ou les nœuds du chemin : l’arbre vide a alors hauteur zéro et une feuille hauteur un. Pour un arbre non vide, les deux mesures diffèrent d’une unité. Dans un exercice, annoncez ou reprenez la convention avant de calculer.

La hauteur ne dépend pas des valeurs inscrites dans les nœuds. Remplacer l’étiquette 8 par 800 ne crée ni chemin ni nœud. Un dessin incliné ou une chaîne repliée ne modifie pas davantage la structure : suivez les liens parent-enfant, pas les distances mesurées sur la page.

Construire un calcul récursif

Représentons un nœud par un tuple (valeur, gauche, droite), et l’absence de nœud par None. Les fonctions inspectent d’abord le cas vide, puis appellent leurs versions sur les deux enfants. Les valeurs remontent depuis les feuilles : il faut connaître les résultats des sous-arbres avant de calculer ceux de leur parent.

def taille(a):
    if a is None:
        return 0
    return 1 + taille(a[1]) + taille(a[2])

def hauteur(a):
    if a is None:
        return -1
    return 1 + max(hauteur(a[1]), hauteur(a[2]))

Le maximum choisit le chemin le plus profond ; l’addition des deux hauteurs n’aurait pas ce sens. Chaque appel travaille sur un sous-arbre strictement plus petit, ce qui assure la terminaison sur un arbre fini.

Comprendre les encadrements

Un arbre binaire de hauteur h en arêtes contient au moins h+1 nœuds, ceux d’un plus long chemin, et au plus 2 puissance (h+1) moins un nœuds lorsqu’il remplit tous les niveaux. Une chaîne de six nœuds a hauteur cinq ; les six nœuds de notre exemple ont hauteur deux.

Pour calculer taille et hauteur avec ces fonctions, chaque nœud est visité : le temps est linéaire en la taille. La pile récursive dépend surtout de la hauteur, puisque seuls les appels sur un chemin restent simultanément en attente. Cette différence entre total visité et profondeur active sera utile pour analyser d’autres algorithmes sur les arbres.

Exemple suivi : faire remonter deux mesures

Prenons une racine A, son enfant gauche B avec une seule feuille D, et son enfant droit C qui est une feuille. Pour chaque feuille C et D, notez le couple (taille,hauteur)=(1,0). B reçoit (1,0) d’un côté et (0,-1) du côté vide ; il produit (2,1). A reçoit (2,1) et (1,0), puis produit (4,2). Le tableau est construit des feuilles vers la racine, dans l’ordre où les dépendances deviennent disponibles.

Les opérations n’ont pas le même sens : les tailles s’ajoutent parce que chaque nœud doit être compté, tandis que les hauteurs sont comparées parce qu’un chemin descendant choisit une branche. Pour une racine possédant deux longues chaînes de hauteur deux, additionner les hauteurs donnerait cinq, alors que le plus long chemin contient trois arêtes. Un exemple asymétrique rend cette différence particulièrement visible.

Exemple suivi : déduire une hauteur possible à partir d’une taille

Avec dix nœuds, une hauteur de deux arêtes est impossible : les trois niveaux ne peuvent contenir que 1+2+4=7 nœuds. Une hauteur de trois devient possible, car quatre niveaux peuvent en contenir quinze. La hauteur maximale vaut neuf, réalisée par une chaîne. On obtient donc une hauteur comprise entre trois et neuf, selon la forme de l’arbre.

Le mot « possible » demande une construction ou une capacité suffisante, et le mot « impossible » demande une borne. Pour quinze nœuds avec hauteur trois, tous les niveaux sont nécessairement pleins puisque la capacité maximale est atteinte. Une taille identique ne détermine généralement pas la hauteur, mais certaines égalités contraignent fortement la structure. L’atelier juxtapose un dessin et les résultats récursifs ; le dessin peut être replié pour rester lisible sans changer les chemins logiques.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Confondre taille et hauteur.

La taille additionne tous les nœuds ; la hauteur retient un plus long chemin.

Oublier la convention de hauteur.

Arêtes et niveaux diffèrent d’une unité pour un arbre non vide.

Cette notion au bac

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

• Bac 2026 · Polynésie · Jour 1 : Annuaire téléphonique : construire et parcourir un ABR

Le prochain pas

• Parcourir un arbre binaire
• Arbres binaires de recherche : rechercher et insérer

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.