Parcours d’un arbre binaire

Ce matériel couvre les parcours d’un arbre binaire, leurs définitions, algorithmes récursifs, représentation en machine, complexité, et application au tri. Il s’adresse aux étudiants en informatique ou mathématiques souhaitant comprendre les bases des arbres binaires et leurs parcours, ainsi que leur utilisation dans le tri.

Définitions et types de parcours d’un arbre binaire

Un arbre binaire est un arbre avec une racine où chaque nœud a au plus deux fils : un fils gauche et un fils droit.

On définit trois parcours principaux des sommets d’un arbre binaire, basés sur une balade autour de l’arbre :

• Parcours préfixe : on liste chaque sommet la première fois qu’on le rencontre.
• Parcours postfixe : on liste chaque sommet la dernière fois qu’on le rencontre.
• Parcours infixe : on liste chaque sommet ayant un fils gauche la deuxième fois qu’on le voit, et chaque sommet sans fils gauche la première fois qu’on le voit.

Exemple de parcours sur un arbre donné :

• Préfixe : r, a, c, h, d, i, j, b, e, k, f
• Postfixe : h, c, i, j, d, a, k, e, f, b, r
• Infixe : c, h, a, i, d, j, r, k, e, b, f

Seconde définition des parcours : passage autour du nœud

En ajoutant des fils fantômes pour les fils manquants, on peut considérer qu’on passe :

• Une fois à gauche de chaque nœud (en descendant) : correspond au parcours préfixe.
• Une fois en-dessous de chaque nœud : correspond au parcours infixe.
• Une fois à droite de chaque nœud (en remontant) : correspond au parcours postfixe.

Cette définition permet de comprendre les parcours comme des moments précis du passage autour du nœud.

Algorithmes récursifs des parcours

Chaque parcours peut être défini récursivement sur un arbre binaire T de racine r :

Parcours préfixe

ParcoursPréfixe(Arbre binaire T de racine r)
  Afficher clef[r]
  ParcoursPréfixe(fils_gauche[r])
  ParcoursPréfixe(fils_droit[r])

Parcours postfixe

ParcoursPostfixe(Arbre binaire T de racine r)
  ParcoursPostfixe(fils_gauche[r])
  ParcoursPostfixe(fils_droit[r])
  Afficher clef[r]

Parcours infixe

ParcoursInfixe(Arbre binaire T de racine r)
  ParcoursInfixe(fils_gauche[r])
  Afficher clef[r]
  ParcoursInfixe(fils_droit[r])

Représentation en machine d’un arbre binaire

Chaque nœud x est représenté par un objet avec :

• clef[x] : valeur associée au nœud
• père[x] : pointeur vers le père (NIL si racine)
• fils_gauche[x] : pointeur vers le fils gauche (NIL si absent)
• fils_droit[x] : pointeur vers le fils droit (NIL si absent)

L’arbre T est référencé par racine[T]. Si racine[T] = NIL, l’arbre est vide.

Complexité du parcours infixe

Considérons un arbre binaire avec n nœuds. Le parcours infixe s’écrit :

Parcours_Infixe(Arbre binaire T de racine x)
  Si x ≠ NIL alors
    Parcours_Infixe(fils_gauche[x])
    Afficher clef[x]
    Parcours_Infixe(fils_droit[x])
  FinSi

On note T(n) le temps pour parcourir un sous-arbre de taille n. On a :

T(n) = T(k) + T(n - k - 1) + d

avec k la taille du sous-arbre gauche, d un temps constant pour afficher la clef, et c un temps constant pour un sous-arbre vide.

Par récurrence, on obtient :

T(n) = (c + d) × n + c

Ce qui montre que le parcours infixe prend un temps en Θ(n).

Notation polonaise inverse et parcours d’arbres d’expressions

Considérons l’arbre d’expression suivant :

        ÷
       /   \
      ×     +
     / \   / \
    +   − e   f
   / \ / \
  a  b c  d

Les parcours des sommets sont :

• Préfixe (notation polonaise) : ÷, ×, +, a, b, −, c, d, +, e, f
• Postfixe (notation polonaise inverse) : a, b, +, c, d, −, ×, e, f, +, ÷
• Infixe (avec parenthèses pour lever les ambiguïtés) : (a + b) × (c − d) ÷ (e + f)

La convention pour l’infixe est d’ajouter une parenthèse ouvrante en entrant dans un sous-arbre et une parenthèse fermante en le quittant, sauf pour les feuilles.

Les parcours préfixe et postfixe représentent les opérateurs comme des fonctions appliquées à leurs arguments, respectivement en notation polonaise et polonaise inverse.

Le tri du bijoutier avec un arbre binaire de recherche

On dispose d’une liste de nombres, par exemple : 7, 9, 3, 5, 4, 1, 8.

Chaque élément n est associé à un nœud v avec :

• père[v] = NIL
• fils_gauche[v] = NIL
• fils_droit[v] = NIL
• clef[v] = n

L’algorithme d’insertion dans l’arbre binaire de recherche est :

Arbre_Insérer(Arbre T, nœud z)
  y := NIL
  x := racine[T]
  TantQue x ≠ NIL faire
    y := x
    Si clef[z] < clef[x] alors
      x := fils_gauche[x]
    Sinon
      x := fils_droit[x]
    FinSi
  FinTantQue
  père[z] := y
  Si y = NIL alors
    racine[T] := z
  Sinon
    Si clef[z] < clef[y] alors
      fils_gauche[y] := z
    Sinon
      fils_droit[y] := z
    FinSi
  FinSi

En appliquant cet algorithme aux éléments de la liste dans l’ordre, on obtient l’arbre :

      7
     / \
    3   9
   / \
  1   5
     / \
    4   8

Le parcours infixe de cet arbre affiche les éléments dans l’ordre trié :

1, 3, 4, 5, 7, 8, 9

Nombre de comparaisons dans la construction de l’arbre

• Pire cas (liste triée) : le nombre de comparaisons est 1 + 2 + ... + (n-1) = ½ n(n-1), soit O(n²).
• Cas optimal (arbre binaire complet) : la profondeur est h = log₂(n+1) - 1, et le nombre total de comparaisons est environ (log₂(n+1) - 1) × (n + 1) + 2, soit en O(n log n).

Le tri par arbre binaire de recherche a donc une complexité comparable au tri rapide (quick sort) en moyenne, avec un avantage en espace pour le quick sort qui trie sur place.

Glossaire des termes clés

• Arbre binaire : structure arborescente où chaque nœud a au plus deux fils, un gauche et un droit.
• Racine : nœud principal de l’arbre, sans père.
• Fils gauche / fils droit : sous-arbres respectivement à gauche et à droite d’un nœud.
• Parcours préfixe : visite des nœuds en affichant la clef avant de parcourir les fils.
• Parcours infixe : visite des nœuds en affichant la clef entre la visite du fils gauche et celle du fils droit.
• Parcours postfixe : visite des nœuds en affichant la clef après avoir parcouru les fils.
• Fils fantôme : fils virtuel ajouté pour représenter l’absence d’un fils réel.
• Notation polonaise : écriture préfixe des expressions, opérateurs avant leurs arguments.
• Notation polonaise inverse : écriture postfixe des expressions, opérateurs après leurs arguments.
• Arbre binaire de recherche : arbre binaire où pour chaque nœud, les clefs du sous-arbre gauche sont plus petites, celles du sous-arbre droit plus grandes.
• Complexité temporelle : mesure du temps d’exécution d’un algorithme en fonction de la taille des données.
• Comparaison : opération consistant à comparer deux clefs pour déterminer leur ordre.

Points clés à retenir

• Les parcours préfixe, infixe et postfixe correspondent à des moments précis du passage autour d’un nœud.
• Les parcours peuvent être définis récursivement de manière simple et élégante.
• Le parcours infixe d’un arbre binaire de recherche affiche les clefs dans l’ordre croissant.
• La complexité du parcours infixe est linéaire en le nombre de nœuds, Θ(n).
• La construction d’un arbre binaire de recherche peut nécessiter jusqu’à O(n²) comparaisons dans le pire cas, mais en moyenne O(n log n).
• La notation polonaise et polonaise inverse sont liées aux parcours préfixe et postfixe des arbres d’expression.