Visualiser un arbre avec Graphviz — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 9)

Visualiser un arbre avec Graphviz

Arbres binaires de recherche de coût minimum · niveau 1 (application)

Énoncé

Le logiciel Graphviz (site graphviz.org) dessine un graphe décrit par la liste de ses arcs, par exemple :


digraph abr { 6 -> 3; 6 -> 8; 3 -> 1; 3 -> 4; 1 -> 0; 1 -> 2; 4 -> 5; 8 -> 7; }

Écrire une fonction récursive void arcs(AB a) qui affiche les arcs de l'arbre $a$ sous cette forme, et l'appliquer à l'abr de coût minimum du cours ( $F = [2, 3, 1, 8, 5, 4, 6, 7, 9]$ ).

Corrigé

Un arc relie chaque racine à chacun de ses sous-arbres non vides ; on traite la racine puis, récursivement, les deux sous-arbres.


static void arcs(AB a) {
    if (vide(a)) return;                                   // pas d'arc
    if (!vide(sag(a))) System.out.print(vr(a) + " -> " + vr(sag(a)) + "; ");
    if (!vide(sad(a))) System.out.print(vr(a) + " -> " + vr(sad(a)) + "; ");
    arcs(sag(a)); arcs(sad(a));                            // les arcs des sous-arbres
}
// appel : System.out.print("digraph abr { "); arcs(a); System.out.println("}");


digraph abr { 6 -> 3; 6 -> 8; 3 -> 1; 3 -> 4; 1 -> 0; 1 -> 2; 4 -> 5; 8 -> 7; }

Un arbre de $n$ valeurs a $n - 1$ arcs ; la fonction est en $Θ (n)$ .