53

アプリのパフォーマンスを改善しようとしています。次のノード クラスを使用して、呼び出しのツリーの形式でパフォーマンス情報を取得しました。

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

この質問のように、ノード間の線が見えるようにツリーを印刷したいと思います。それを行うために C# で使用できるアルゴリズムは何ですか?

編集:明らかに再帰を使用する必要があります-しかし、私の試みは行を間違った場所に置き続けます。私が求めているのは、ツリーを適切な方法で印刷する特定のアルゴリズムです。垂直線を印刷するタイミングと水平線を印刷するタイミングの詳細です。

編集:文字列のコピーを使用してノードをインデントするだけでは不十分です。私は探していません

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

そうでなければならない

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

ツリー構造が表示されている限り、または同様のもの。C と D は G とは異なる方法でインデントされていることに注意してください。繰り返し文字列を使用してノードをインデントすることはできません。

4

8 に答える 8

94

トリックは、文字列をインデントとして渡し、最後の子を特別に扱うことです:

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);
   }
}

このように呼び出された場合：

root.PrintPretty("", true);

このスタイルで出力します:

\-root
  \-child
    |-child
    \-child
      |-child
      |-child
      \-child
        |-child
        |-child
        | |-child
        | \-child
        |   |-child
        |   |-child
        |   |-child
        |   \-child
        |     \-child
        |       \-child
        \-child
          |-child
          |-child
          |-child
          | \-child
          \-child
            \-child
于 2009-10-30T11:12:47.430 に答える
36

再帰あり

ツリーを深く掘り下げるにつれて変更されるインデント文字列を追跡する必要があります。余分な文字を追加しないよう|にするには、ノードがそのセットの最後の子であるかどうかも知る必要があります。

public static void PrintTree(Node tree, String indent, Bool last)
{
    Console.Write(indent + "+- " + tree.Name);
    indent += last ? "   " : "|  ";

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

このように呼び出された場合：

PrintTree(node, "", true)

次のようなテキストが出力されます。

+- 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

再帰なし

非常に深いツリーがあり、コール スタックのサイズが制限されている場合は、代わりに静的で非再帰的なツリー トラバーサルを実行して、同じ結果を出力できます。

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));
            }
        }
    }
}
于 2011-12-19T21:04:17.460 に答える
12

PrintNode メソッドを作成し、再帰を使用します。

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 + "   |");
    }
}

Aそして、ツリー全体を印刷するには、次のコマンドを実行します:

topNode.PrintNode("");

私の例では、次のような結果が得られます。

 + 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
于 2009-10-30T10:48:13.287 に答える
8

@Willによる（現在受け入れられている）回答のバリエーションを次に示します。変更点は次のとおりです。

  1. これは、ASCII の代わりに Unicode 記号を使用して、より快適な外観を実現します。
  2. ルート要素はインデントされません。
  3. グループの最後の子には、その後に「空白」行が追加されます (視覚的に解析しやすくなります)。

C++ 以外で簡単に使用できるように、疑似コードとして提示します。

def printHierarchy( item, indent )
  kids = findChildren(item)  # get an iterable collection
  labl = label(item)         # the printed version of the item
  last = isLastSibling(item) # is this the last child of its parent?
  root = isRoot(item)        # is this the very first item in the tree?

  if root then
    print( labl )
  else
    # Unicode char U+2514 or U+251C followed by U+2574
    print( indent + (last ? '└╴' : '├╴') + labl )

    if last and isEmpty(kids) then
      # add a blank line after the last child
      print( indent ) 
    end

    # Space or U+2502 followed by space
    indent = indent + (last ? '  ' : '│ ')
  end

  foreach child in kids do
    printHierarchy( child, indent )
  end
end

printHierarchy( root, "" )

サンプル結果:

Body
├╴PaintBlack
├╴CarPaint
├╴Black_Material
├╴PaintBlue
├╴Logo
│ └╴Image
│
├╴Chrome
├╴Plastic
├╴Aluminum
│ └╴Image
│
└╴FabricDark
于 2014-11-26T04:34:31.790 に答える
6

次の方法を使用して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 + "|  ");
}

以下は出力です。

+- 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>
于 2013-08-30T00:51:41.833 に答える