Comment calculer la hauteur d’un arbre binaire ?

Réponse courte

Repère la racine, puis compte les arêtes sur chaque chemin jusqu’à une feuille. La hauteur est le plus grand de ces nombres ; ici, une racine seule a une hauteur 0.

Comprendre

Fixe la convention

La hauteur dépend de la manière de mesurer. Avec la convention en arêtes, la profondeur d’un nœud est le nombre de liens du chemin qui le relie à la racine. La hauteur de l’arbre est la profondeur maximale. La racine a donc profondeur 0 et, si elle est seule, l’arbre a hauteur 0. Certains supports comptent plutôt les niveaux ; ne mélange pas leurs résultats sans convertir la convention.

Procédure de calcul

Commence à la racine et suis séparément chaque branche descendante jusqu’à ses feuilles. Pour chaque chemin, compte les arêtes, puis garde le maximum. Il n’est pas nécessaire d’additionner les longueurs des branches. Par exemple, si A a pour enfants B et C, B a D et E, et C a F, les chemins les plus longs sont A-B-D, A-B-E et A-C-F : chacun a deux arêtes. La hauteur vaut 2.

Contrôle sur la représentation

Une feuille isolée a une hauteur 0, car aucun lien ne la sépare de son propre point de départ. Dans un arbre vide, certaines définitions posent la hauteur à −1 pour que la formule récursive fonctionne ; vérifie ce que le sujet demande avant d’utiliser ce cas. Ne mesure ni la taille dessinée d’une branche ni le nombre total de nœuds : seule compte la profondeur maximale en liens.

Étapes

  1. Annonce la convention retenue : hauteur mesurée en arêtes.
  2. Trace ou énumère les chemins de la racine jusqu’aux feuilles.
  3. Compte les arêtes sur chaque chemin et retiens le maximum.

Exemples

  • Pour A-B-D et A-B-E, chaque chemin compte deux arêtes : hauteur 2.
  • Pour une chaîne R-S-T-U, le chemin maximal a trois arêtes : hauteur 3.

Pièges fréquents

  • Prendre le premier chemin trouvé sans examiner les autres branches : une branche plus profonde peut fixer la hauteur.
  • Compter les nœuds du chemin : A-B-D comporte trois nœuds, mais seulement deux arêtes.

Et maintenant ?

Questions proches

← Toutes les questions-réponses