Parcours en profondeur des arbres

Le parcours en profondeur est très facile à programmer dans sa version récursive ; s'il s'agit simplement d'imprimer les valeurs des nuds, un par ligne, on écrira :

void depth_first_rec(tree p) {
    if (!is_empty_tree(p)) {
      cout << p->label << endl;
      depth_first_rec(p->left);
      depth_first_rec(p->right);
    }
}

Pour une utilisation plus générale du parcours en profondeur, on peut passer une procédure en paramètre, qui opère sur la valeur de chaque nud :

void depth_first_rec(tree p, void f(data)) {
    if (!is_empty_tree(p)) {
      f(p->label);
      depth_first_rec(p->left, f);
      depth_first_rec(p->right, f);
    }
}

Il s'agit en fait de l'ordre préfixe de ce parcours, où chaque nud de l'arbre est traité avant ses descendants.

L'application de cet ordre à l'arbre de la figure 20 donne comme résultat : 1, 2, 4, 8, 5, 3, 6, 9, 10, 12, 13, 7, 11. Pour obtenir l'ordre infixe, où chaque nud est traité entre ses descendants gauches et ses descendants droits, et l'ordre postfixe, où chaque nud est traité après tous ses descendants, il suffit de déplacer l'appel à la fonction f ; on obtient

    depth_first_rec(p->left, f);
    f(p->label);
    depth_first_rec(p->right, f);

pour l'ordre infixe, qui donne comme résultat sur l'arbre de la figure 20 4, 8, 2, 5, 1, 9, 6, 12, 10, 13, 3, 11, 7, ainsi que

    depth_first_rec(p->left, f);
    depth_first_rec(p->right, f);
    f(p->label);

pour l'ordre postfixe, qui donne comme résultat 8, 4, 5, 2, 9, 12, 13, 10, 6, 11, 7, 3, 1.