Arbres binaires : vocabulaire et mesures

Un arbre binaire est formé de nœuds reliés de façon hiérarchique :

• un nœud particulier, la racine, est au sommet ;
• chaque nœud a au plus deux fils : un fils gauche et un fils droit ;
• le fils gauche est la racine du sous-arbre gauche, le fils droit celle du sous-arbre droit ;
• une feuille est un nœud sans aucun fils.

Exemple, avec A pour racine (« — » : pas de fils) :

        A
      /   \
     B     C
    /     / \
   D     E   F
          \
           G

Les feuilles sont D, F et G. Les arbres modélisent des situations hiérarchiques : l'arborescence des dossiers et fichiers, une expression arithmétique (chaque opération a pour fils ses deux opérandes).

• La taille est le nombre de nœuds.
• La hauteur dépend d'une convention à préciser. Ici : un arbre réduit à sa racine a pour hauteur 1, l'arbre vide 0. La hauteur est alors le nombre de nœuds du plus long chemin de la racine à une feuille.

Compter sur le tableau. La taille se lit directement : une ligne par nœud. Pour la hauteur, on range les nœuds par niveau : la racine au niveau 1, ses fils au niveau 2, leurs fils au niveau 3, et ainsi de suite ; avec la convention ci-dessus, la hauteur est le numéro du niveau le plus bas. Pour l'arbre de racine A : niveau 1 : A ; niveau 2 : B, C ; niveau 3 : D, E, F ; niveau 4 : G. La hauteur vaut 4. Le sous-arbre droit de A, de racine C, a pour taille 4 (C, E, F, G) et pour hauteur 3.

Les algorithmes qui calculent ces mesures par programme (fonctions récursives) sont l'objet de la leçon « Arbres binaires : taille, hauteur et parcours ».

Encadrement. Pour un arbre binaire non vide de hauteur h et de taille n : h ⩽ n ⩽ 2ʰ − 1. Le minimum est atteint par un arbre « filiforme » (un seul nœud par niveau), le maximum par un arbre complet (1 + 2 + 4 + … + 2ʰ⁻¹ nœuds). Ici, h = 4 et n = 7 : 4 ⩽ 7 ⩽ 15.

Énoncé. Pour l'arbre du tableau ci-dessus, donner la taille, la hauteur (racine seule : hauteur 1) et le nombre de feuilles.

Résolution.

1. Taille : chaque ligne du tableau décrit un nœud ; il y en a 7.
2. Feuilles : les nœuds avec deux « — » sont D, F et G : 3 feuilles.
3. Hauteur : on cherche le plus long chemin de la racine à une feuille. A → B → D compte 3 nœuds ; A → C → F en compte 3 ; A → C → E → G en compte 4. La hauteur vaut 4.

On compte les nœuds du chemin, pas les arêtes (il y en a 3 sur A → C → E → G) : c'est la convention annoncée.

Chaque niveau peut contenir deux fois plus de nœuds que le précédent : un arbre de hauteur 4 a au plus 15 nœuds.