Files et parcours en largeur des arbres

L'autre façon de parcourir un arbre est en largeur (d'abord). Les nuds de la figure 20 ont été numérotés dans l'ordre du parcours en largeur : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.

On ne peut pas programmer récursivement ce parcours de façon naturelle. La version itérative utilise la structure de file au lieu de celle de pile.

void breadth_first(tree p, void f(data)) {
  queue q;

  mk_empty_queue (q);
  in(p, q);
  while (!is_empty_queue (q)) {
    p = out(q);
    if (!is_empty_tree(p)) {
      f(p->label);
      in(p->left, q);
      in(p->right, q);
    }
  }
}

Cette fonction a exactement la même forme que depth_first_iter, les piles étant simplement remplacées par les files, avec leurs opérations : ceci est un indice du pouvoir << structurant >> des structures de données.