Le parcours en largeur

(* Renvoie les etiquettes de a niveau par niveau, de gauche a droite.
   La file est realisee par DEUX listes : `avant` d'ou l'on sort,
   `arriere` ou l'on entre a l'envers. Complexite : Theta(n) amorti. *)
let largeur a =
  let rec aux avant arriere acc =
    match avant, arriere with
    | [], [] -> List.rev acc
    | [], _ -> aux (List.rev arriere) [] acc        (* on retourne la file *)
    | Vide :: r, ar -> aux r ar acc
    | Noeud (g, e, d) :: r, ar -> aux r (d :: g :: ar) (e :: acc)
  in aux [a] [] []

Mesure : sur l'arbre de l'exercice 10.1, le résultat est $8,3,9,1,6,7,4$.

Pourquoi il n'est pas récursif comme les autres. Les trois parcours en profondeur ont une propriété que celui-ci n'a pas : le parcours d'un arbre est fait des parcours de ses sous-arbres, mis bout à bout. C'est ce qui permet d'écrire prefixe g @ prefixe d.

En largeur, c'est faux. Le parcours en largeur de l'arbre de l'exercice est $8,3,9,1,6,7,4$. Celui du sous-arbre gauche est $3,1,6,4$, celui du droit $9,7$. Les deux listes sont entrelacées, pas concaténées : le $9$ du sous-arbre droit s'insère entre le $3$ et le $1$ du gauche. Aucune fonction récursive sur la structure ne peut produire cet entrelacement, parce que l'information nécessaire — le niveau — ne remonte pas des fils vers le père.

La structure qui convient est la file, et le contraste avec la profondeur est exact :

Un parcours en profondeur peut employer la pile d'appels et se dispenser d'une structure explicite — c'est ce que fait la récursion, et c'est la remarque du cours sur les blocs d'activation. Le parcours en largeur n'a pas cette chance : la pile d'appels est une pile, et il lui faut une file. Il faut donc toujours l'écrire à la main, en OCaml comme en C.

Sur la réalisation de la file. Les deux listes ne sont pas une coquetterie : une file réalisée par une seule liste avec ajout en queue coûterait $\Theta (n)$ par insertion, donc $\Theta (n^2)$ au total — le défaut du @ de l'exercice 10.5, à nouveau. Avec deux listes, chaque nœud est déplacé au plus une fois de arriere vers avant : le coût est $\Theta (1)$ amorti, donc $\Theta (n)$ au total. C'est la structure du chapitre chap:sequentielles, et c'est ici qu'elle sert.

Le coût en mémoire, qui est l'autre différence. Un parcours en profondeur occupe $O(h)$. Un parcours en largeur occupe la largeur maximale de l'arbre, soit $O(n)$ dans le pire cas — un arbre parfait a $n/2$ nœuds au dernier niveau. Sur un arbre équilibré, la profondeur est donc économe et la largeur coûteuse ; sur un peigne, c'est l'inverse. Aucun des deux ne domine.