Comment imprimer une arborescence?

Question

Je suis en train d'améliorer les performances de notre application. J'ai des informations de performance sous la forme d'un arbre d'appels, avec le nœud suivant de la classe:

public class Node
{
    public string Name; // method name
    public decimal Time; // time spent in method
    public List<Node> Children;
}

Je veux imprimer l'arbre tel que je vois les lignes entre les nœuds - quelque chose de similaire à cette question. Qu'est ce qu'un algorithme que je peux utiliser en C# pour le faire?

Edit: Évidemment, j'ai besoin d'utiliser la récursivité - mais mes tentatives continuer à mettre les lignes dans les mauvais endroits. Ce que je demande, c'est un algorithme spécifique qui va imprimer l'arbre dans une belle manière - le moment d'imprimer une ligne verticale et lors de l'impression d'une horizontale.

Edit: Il ne suffit pas juste d'utiliser des copies d'une chaîne de retrait de nœuds. Je ne suis pas à la recherche pour

A
|-B
|-|-C
|-|-D
|-|-|-E
|-F
|-|-G

il doit être

A
+-B
| +-C
| +-D
|   +-E
+-F
  +-G

ou quelque chose de semblable, tant que la structure de l'arbre est visible. Notez que C et D sont en retrait différemment à G - je ne peux pas juste l'utilisation répétée de la chaîne de retrait de nœuds.

Answer 1

L'astuce consiste à passer une chaîne en tant qu'indent et à traiter spécialement le dernier enfant:

 class Node
{    
   public void PrintPretty(string indent, bool last)
   {
       Console.Write(indent);
       if (last)
       {
           Console.Write("\\-");
           indent += "  ";
       }
       else
       {
           Console.Write("|-");
           indent += "| ";
       }
       Console.WriteLine(Name);

       for (int i = 0; i < Children.Count; i++)
           Children[i].PrintPretty(indent, i == Children.Count - 1);
   }
}
 

Si appelé comme ça:

 root.PrintPretty("", true);
 

affichera dans ce style:

 \-root
  \-child
    |-child
    \-child
      |-child
      |-child
      \-child
        |-child
        |-child
        | |-child
        | \-child
        |   |-child
        |   |-child
        |   |-child
        |   \-child
        |     \-child
        |       \-child
        \-child
          |-child
          |-child
          |-child
          | \-child
          \-child
            \-child
 

Answer 2

Si vous avez une arborescence très profonde et que la taille de votre pile d'appels est limitée, vous pouvez effectuer une traversée d'arborescence statique et non récursive, comme suit:

 public static void PrintTree(Node tree)
{
    List<Node> firstStack = new List<Node>();
    firstStack.Add(tree);

    List<List<Node>> childListStack = new List<List<Node>>();
    childListStack.Add(firstStack);

    while (childListStack.Count > 0)
    {
        List<Node> childStack = childListStack[childListStack.Count - 1];

        if (childStack.Count == 0)
        {
            childListStack.RemoveAt(childListStack.Count - 1);
        }
        else
        {
            tree = childStack[0];
            childStack.RemoveAt(0);

            string indent = "";
            for (int i = 0; i < childListStack.Count - 1; i++)
            {
                indent += (childListStack[i].Count > 0) ? "|  " : "   ";
            }

            Console.WriteLine(indent + "+- " + tree.Name);

            if (tree.Children.Count > 0)
            {
                childListStack.Add(new List<Node>(tree.Children));
            }
        }
    }
}
 

Ce qui donnerait quelque chose comme ça:

 +- root
   +- branch-A
   |  +- sibling-X
   |  |  +- grandchild-A
   |  |  +- grandchild-B
   |  +- sibling-Y
   |  |  +- grandchild-C
   |  |  +- grandchild-D
   |  +- sibling-Z
   |     +- grandchild-E
   |     +- grandchild-F
   +- branch-B
      +- sibling-J
      +- sibling-K
 

Answer 3

Créez la méthode PrintNode et utilisez la récursivité:

 class Node
{
    public string Name;
    public decimal Time;
    public List<Node> Children = new List<Node>();

    public void PrintNode(string prefix)
    {
        Console.WriteLine("{0} + {1} : {2}", prefix, this.Name, this.Time);
        foreach (Node n in Children)
            if (Children.IndexOf(n) == Children.Count - 1)
                n.PrintNode(prefix + "    ");
            else
                n.PrintNode(prefix + "   |");
    }
}
 

Puis, pour imprimer l’arbre entier, exécutez simplement:

 topNode.PrintNode("");
 

Dans mon exemple, cela nous donnerait quelque chose comme ça:

  + top : 123
   | + Node 1 : 29
   |   | + subnode 0 : 90
   |   |     + sdhasj : 232
   |   | + subnode 1 : 38
   |   | + subnode 2 : 49
   |   | + subnode 8 : 39
   |     + subnode 9 : 47
     + Node 2 : 51
       | + subnode 0 : 89
       |     + sdhasj : 232
       | + subnode 1 : 33
         + subnode 3 : 57
 

Answer 4

J'utilise la méthode suivante pour imprimer un fichier BST

 private void print(Node root, String prefix) {
    if (root == null) {
    System.out.println(prefix + "+- <null>");
    return;
    }

    System.out.println(prefix + "+- " + root);
    print(root.left, prefix + "|  ");
    print(root.right, prefix + "|  ");
}
 

Voici la sortie.

 +- 43(l:0, d:1)
|  +- 32(l:1, d:3)
|  |  +- 10(l:2, d:0)
|  |  |  +- <null>
|  |  |  +- <null>
|  |  +- 40(l:2, d:2)
|  |  |  +- <null>
|  |  |  +- 41(l:3, d:0)
|  |  |  |  +- <null>
|  |  |  |  +- <null>
|  +- 75(l:1, d:5)
|  |  +- 60(l:2, d:1)
|  |  |  +- <null>
|  |  |  +- 73(l:3, d:0)
|  |  |  |  +- <null>
|  |  |  |  +- <null>
|  |  +- 100(l:2, d:4)
|  |  |  +- 80(l:3, d:3)
|  |  |  |  +- 79(l:4, d:2)
|  |  |  |  |  +- 78(l:5, d:1)
|  |  |  |  |  |  +- 76(l:6, d:0)
|  |  |  |  |  |  |  +- <null>
|  |  |  |  |  |  |  +- <null>
|  |  |  |  |  |  +- <null>
|  |  |  |  |  +- <null>
|  |  |  |  +- <null>
|  |  |  +- <null>