如何打印树形结构？

Question

我正在尝试提高应用程序的性能.我有一个调用树形式的性能信息,具有以下节点类:

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不同 - 我不能只使用重复的字符串来缩进节点.

Answer 1

诀窍是传递一个字符串作为缩进并特别处理最后一个孩子:

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

Answer 2

随着递归

您需要跟踪在深入树中时修改的缩进字符串.为了避免添加额外的|字符,您还需要知道Node是否是该集合中的最后一个子节点.

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

Answer 3

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

然后打印整个树只执行:

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

Answer 4

以下是@Will对(当前接受的)答案的修改.变化是:

1. 这使用Unicode符号而不是ASCII来获得更令人愉悦的外观.
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

Answer 5

我正在使用以下方法来打印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>