Comment imprimer un arbre de manière bien formatée?

Question

Quel est le moyen le plus simple d'imprimer un arbre dans sa structure arborescente? Tels que ...

    some root 
      / |   \ 
      child1 child2  child 3 
     /
     anotherchild    /\ 
          yup  another 

Même le formatage à la main est difficile. Comment faire pour qu'un programme imprime un arbre de cette façon?

Answer 1

Eh bien, vous pouvez essayer quelque chose comme var_dump PHP - si vous essayez var_dump sur un tableau en forme d'arbre, il vous donnera une représentation équitable de cet arbre, qui est la suivante:

root { 
    child1 { 
     anotherchild 
    } 
    child2 
    child3 { 
     yup 
     another 
    } 
} 

Answer 2

Bien que je n » t l'essayer moi-même, graphviz a un texte en clair output format.

Answer 3

À moins de disposer d'une bibliothèque graphique agréable que vous pouvez utiliser, vous aurez beaucoup de mal à représenter une hiérarchie de la manière que vous décrivez.

En supposant que vous vouliez l'imprimer sur la console, ou sur un fichier, vous devrez composer avec le pré-calcul de la longueur de tous les éléments de données dans l'arbre entier afin de les aligner correctement. Et comment gérez-vous des choses comme le line-wrap?

Un bien meilleur moyen est de représenter l'arbre verticalement, en utilisant l'indentation pour montrer un élément enfant.

Root 
    - Child1 
     - Grandchild1 
     - Grandchild2 
    - Child2 
     - Grandchild3 
     - Grandchild4 

Ceci est beaucoup plus simple à coder, et plus tolérant des choses comme linewrap - comme il n'y a jamais un élément sur une ligne. C'est ainsi qu'un document de navigateur de dossiers ou de document XML peut afficher ses données hiérarchiques.

Pour le faire de cette façon, vous faites un parcours en profondeur d'abord et avant l'étape récursive imprimer le nœud:

public void PrintNode(TreeNode node) 
{ 
    PrintNode(node, 0); 
} 

private void PrintNode(TreeNode node, int indentation) 
{ 
    // Print the value to the console/file/whatever 
    // This prefixes the value with the necessary amount of indentation 
    Print(node.Value, indentation); 

    // Recursively call the child nodes. 
    foreach(TreeNode childNode in node.Children) 
    { 
     PrintNode(childNode, indentation + 1); // Increment the indentation counter. 
    } 
} 

espoir qui aide

Answer 4

Que diriez-vous this answer à une question similaire? Il imprime un bel arbre ASCII-art.

Ou peut-être this one si vous voulez aller complètement graphique?

Answer 5

Je devais faire ceci l'année dernière en écrivant une application d'arbre généalogique. Trouvé un tutoriel Java en ligne qui a aidé, mais mon Google-Fu m'a échoué aujourd'hui, donc je vais devoir simplement l'expliquer.

Il s'agit simplement d'un algorithme récursif qui ajuste la position du nœud parent en fonction des nœuds enfants. Dans ce pseudocode est quelque chose comme ceci:

positionNode (node,x,y) { 
    foreach (child in node.children) { 
     positionNode(child,x,y+1) 
     x ++ 
    } 
    node.x = (x-1)/2 
    node.y = y 
} 

je ne rappellerons correctement, vous devrez peut-être modifier un peu le code pour obtenir ce droit.

Answer 6

La réponse suivante est en Java, mais il est si simple qu'il peut être facilement retranscrit dans d'autres langues:

public interface Function1<R, T1> 
{ 
    R invoke(T1 argument1); 
} 

public interface Procedure1<T1> 
{ 
    void invoke(T1 argument1); 
} 

public static <T> void dump(T node, Function1<List<T>,T> breeder, 
     Function1<String,T> stringizer, Procedure1<String> emitter) 
{ 
    emitter.invoke(stringizer.invoke(node)); 
    dumpRecursive(node, "", breeder, stringizer, emitter); 
} 

private static final String[][] PREFIXES = { { " ├─ ", " │ " }, { " └─ ", " " } }; 

private static <T> void dumpRecursive(T node, String parentPrefix, 
     Function1<List<T>,T> breeder, Function1<String,T> stringizer, 
     Procedure1<String> emitter) 
{ 
    for(Iterator<T> iterator = breeder.invoke(node).iterator(); iterator.hasNext();) 
    { 
     T childNode = iterator.next(); 
     String[] prefixes = PREFIXES[iterator.hasNext()? 0 : 1]; 
     emitter.invoke(parentPrefix + prefixes[0] + stringizer.invoke(childNode)); 
     dumpRecursive(childNode, parentPrefix + prefixes[1], breeder, stringizer, emitter); 
    } 
} 

Il produit la sortie suivante:

Automobile 
├─ Passenger Vehicle 
│ ├─ Light Passenger Vehicle 
│ │ ├─ Two Wheeled 
│ │ │ ├─ Moped 
│ │ │ ├─ Scooter 
│ │ │ └─ Motorcycle 
│ │ ├─ Three Wheeled 
│ │ └─ Four Wheeled 
│ │  ├─ Car 
│ │  ├─ Station Wagon 
│ │  ├─ Pick-up Truck 
│ │  └─ Sports Utility Vehicle 
│ └─ Heavy Passenger Vehicle 
│  ├─ Bus 
│  │ ├─ Single-Deck Bus 
│  │ │ ├─ Mini Bus 
│  │ │ └─ Big Bus 
│  │ └─ Double-Deck Bus 
│  └─ Coach 
│   ├─ Deluxe 
│   └─ Air-Conditioned 
└─ Goods Vehicle 
    ├─ Light Goods Vehicle 
    │ ├─ Delivery Van 
    │ ├─ Light Truck 
    │ └─ Tempo 
    │  ├─ Three Wheeler Tempo 
    │  └─ Four Wheeler Tempo 
    └─ Heavy Goods Vehicle 
     ├─ Truck 
     └─ Tractor Trailer 

...si vous l'invoquez à l'aide de l'exemple de programme suivant:

final class Scratch 
{ 
    static class Node 
    { 
     String name; 
     List<Node> children; 

     Node(String name, Node... children) 
     { 
      this.name = name; 
      this.children = Arrays.asList(children); 
     } 
    } 

    public static void main(String[] args) 
    { 
     Node tree = new Node("Automobile", 
       new Node("Passenger Vehicle", 
         new Node("Light Passenger Vehicle", 
           new Node("Two Wheeled", 
             new Node("Moped"), 
             new Node("Scooter"), 
             new Node("Motorcycle")), 
           new Node("Three Wheeled"), 
           new Node("Four Wheeled", 
             new Node("Car"), 
             new Node("Station Wagon"), 
             new Node("Pick-up Truck"), 
             new Node("Sports Utility Vehicle"))), 
         new Node("Heavy Passenger Vehicle", 
           new Node("Bus", 
             new Node("Single-Deck Bus", 
               new Node("Mini Bus"), 
               new Node("Big Bus")), 
             new Node("Double-Deck Bus")), 
           new Node("Coach", 
             new Node("Deluxe"), 
             new Node("Air-Conditioned")))), 
       new Node("Goods Vehicle", 
         new Node("Light Goods Vehicle", 
           new Node("Delivery Van"), 
           new Node("Light Truck"), 
           new Node("Tempo", 
             new Node("Three Wheeler Tempo"), 
             new Node("Four Wheeler Tempo"))), 
         new Node("Heavy Goods Vehicle", 
           new Node("Truck"), 
           new Node("Tractor Trailer")))); 
     dump(tree, n -> n.children, n -> n.name, s -> System.out.println(s)); 
    } 
}