如何打印树结构?

I'm trying to improve performance in our app. I've got performance information in the form of a tree of calls, with the following node class:

我正在努力改进我们的应用程序的性能。我有一个调用树的形式的性能信息，有以下节点类:

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

I want to print out the tree such that I can see lines between the nodes - something like in this question. What's an algorithm I can use in C# for doing that?

我想把树打印出来，这样我就能看到节点之间的线了，就像这个问题一样。c#中有什么算法可以用来实现这一点?

Edit: Obviously I need to use recursion - but my attempts keep putting the lines in the wrong places. What I'm asking for is a specific algorithm that will print the tree in a nice manner - the details of when to print a vertical line and when to print a horizontal one.

编辑:显然我需要使用递归——但是我的尝试总是把线放在错误的位置。我想要的是一种特定的算法，它可以以一种很好的方式打印树——具体的细节是什么时候打印一条垂直线，什么时候打印一条水平线。

Edit: It isn't sufficient just to use copies of a string to indent the nodes. I'm not looking for

编辑:仅仅使用字符串的拷贝来缩进节点是不够的。我不寻找

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

it has to be

它必须是

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

or anything similar, so long as the tree structure is visible. Notice that C and D are indented differently to G - I can't just use a repeated string to indent the nodes.

或者任何类似的东西，只要树的结构是可见的。注意，C和D的缩进与G不同——我不能仅仅使用重复的字符串来缩进节点。

8 个解决方案

#1

The trick is to pass a string as the indent and to treat the last child specially:

诀窍是把一根线作为缩进，并特别对待最后一个子结点:

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

If called like this:

如果是这样的:

root.PrintPretty("", true);

will output in this 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

#2

With Recursion

You'll need to keep track of an indentation string that's modified as you go deeper into the tree. To avoid adding extra | characters, you'll also need to know whether the Node is the last child in that set.

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

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

When called like this:

调用时这样的:

PrintTree(node, "", true)

It will output text like this:

它将输出如下所示的文本:

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

Without Recursion

If you happen to have a very deep tree and your call stack size is limited, you can instead do a static, non-recursive tree traversal to output the same result:

如果您碰巧有一个非常深的树，并且您的调用堆栈大小是有限的，那么您可以执行静态的、非递归的树遍历来输出相同的结果:

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

#3

Create PrintNode method and use recursion:

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

ANd then to print the whole tree just execute:

然后把整棵树打印出来

topNode.PrintNode("");

In my example it would give us something like that:

在我的例子中，它会给我们这样的东西:

 + 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

#4

i am using the following method to print a BST

我正在使用以下方法打印一个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 + "|  ");
}

Following is the output.

下面是输出。

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

#5

Here is a variation on the (currently-accepted) answer by @Will. The changes are:

以下是@Will给出的(当前接受的)答案的一个变体。的变化是:

1. This uses Unicode symbols instead of ASCII for a more pleasing appearance.
2. 这将使用Unicode符号而不是ASCII来实现更美观的外观。
3. The root element is not indented.
4. 根元素没有缩进。
5. The last child of a group has a 'blank' line added after it (makes it easier to visually parse).
6. 组的最后一个子元素后面添加了一个“空白”行(这样更容易进行可视化解析)。

Presented as pseudo-code for easier consumption outside of C++:

表示为伪代码，便于在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, "" )

Sample result:

结果:样本

Body
├╴PaintBlack
├╴CarPaint
├╴Black_Material
├╴PaintBlue
├╴Logo
│ └╴Image
│
├╴Chrome
├╴Plastic
├╴Aluminum
│ └╴Image
│
└╴FabricDark

#6

This is a generic version of Joshua Stachowski's answer. The good thing about Joshua Stachowski's answer is that it doesn't require the actual node class to implement any extra method and it looks nice as well.

这是Joshua Stachowski的一般性回答。Joshua Stachowski的答案的好处是，它不需要实际的节点类来实现任何额外的方法，而且看起来也很不错。

I made his solution generic which can be used for any type without modifying the code.

我使他的解决方案通用，可以在不修改代码的情况下使用任何类型。

    public static void PrintTree<T>(T rootNode,
                                    Func<T, string> nodeLabel, 
                                    Func<T, List<T>> childernOf)
            {
                var firstStack = new List<T>();
                firstStack.Add(rootNode);

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

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

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

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

                        Console.WriteLine(indent + "+- " + nodeLabel(rootNode));
                        var children = childernOf(rootNode);
                        if (children.Count > 0)
                        {
                            childListStack.Add(new List<T>(children));
                        }
                    }
                }
            }

Usage

使用

 PrintTree(rootNode, x => x.ToString(), x => x.Children);

#7

The best way with full optionality without using recursion is` https://github.com/tigranv/Useful_Examples/tree/master/Directory%20Tree

使用完全可选性而不使用递归的最佳方法是“https://github.com/tigranv/Useful_Examples/tree/master/Directory%20Tree”

public static void DirectoryTree(string fullPath)
    {
    string[] directories = fullPath.Split('\\');
    string subPath = "";
    int cursorUp = 0;
    int cursorLeft = 0;

    for (int i = 0; i < directories.Length-1; i++)
    {
        subPath += directories[i] + @"\";
        DirectoryInfo directory = new DirectoryInfo(subPath);
        var files = directory.GetFiles().Where(f => !f.Attributes.HasFlag(FileAttributes.Hidden)).Select(f => f.Name).ToArray();
        var folders = directory.GetDirectories().Where(f => !f.Attributes.HasFlag(FileAttributes.Hidden)).Select(f => f.Name).ToArray();             
        int longestFolder = folders.Length != 0 ? (folders).Where(s => s.Length == folders.Max(m => m.Length)).First().Length:0;
        int longestFle = files.Length != 0? (files).Where(s => s.Length == files.Max(m => m.Length)).First().Length : 0;
        int longestName =3 + (longestFolder <= longestFle ? longestFle:longestFolder)<=25? (longestFolder <= longestFle ? longestFle : longestFolder) : 26;
        int j = 0;

        for (int k = 0; k < folders.Length; k++)
        {
            folders[k] = folders[k].Length <= 25 ? folders[k] : (folders[k].Substring(0, 22) + "...");

            if (folders[k] != directories[i + 1])
            {
                Console.SetCursorPosition(cursorLeft, cursorUp + j);
                Console.WriteLine("+" + folders[k]);
                j++;
            }
            else
            {
                if (i != directories.Length - 2)
                {
                    Console.SetCursorPosition(cursorLeft, cursorUp + j);
                    Console.WriteLine("-" + folders[k] + new string('-', longestName - directories[i + 1].Length) + "--\u261B");
                    j++;
                }
                else
                {
                    Console.ForegroundColor = ConsoleColor.Red;
                    Console.SetCursorPosition(cursorLeft, cursorUp + j);
                    Console.WriteLine("***"+ folders[k] + "***");
                    Console.ForegroundColor = ConsoleColor.Gray;
                    j++;
                }
            }
        }

        for(int k = 0; k <  files.Length; k++)
        {
            files[k] = files[k].Length <= 25 ? files[k] : (files[k].Substring(0, 22) + "...");
            Console.SetCursorPosition(cursorLeft, cursorUp + j);
            Console.WriteLine("+" + files[k]);
            j++;
        }

        cursorUp += Array.IndexOf(folders, directories[i+1]) + 1;
        cursorLeft += longestName+3;
    }
}

#8

Using (y, x) coordinates

C code here:

C代码:

void printVLine(wchar_t token, unsigned short height, unsigned short y, unsigned short x);
const static wchar_t TREE_VLINE = L'┃';
const static wchar_t TREE_INBRANCH[] = L"┣╾⟶ ";
const static wchar_t TREE_OUTBRANCH[] = L"┗╾⟶ ";

typedef void (*Printer)(void * whateverYouWant);
const static unsigned int  INBRANCH_SIZE = sizeof(TREE_INBRANCH) / sizeof(TREE_INBRANCH[0]);
const static unsigned int OUTBRANCH_SIZE = sizeof(TREE_OUTBRANCH) / sizeof(TREE_OUTBRANCH[0]);

size_t Tree_printFancy(Tree * self, int y, int x, Printer print){
    if (self == NULL) return 0L;
    //
    size_t descendants = y;
    move(y, x);
    print(Tree_at(self));
    if (!Tree_isLeaf(self)){ // in order not to experience unsigned value overflow in while()
        move(++y, x); 
        size_t i = 0;
        while(i < Tree_childrenSize(self) - 1){
            wprintf(TREE_INBRANCH);
            size_t curChildren = Tree_printFancy(
                   Tree_childAt(self, i), y, x + INBRANCH_SIZE, print
            );
            printVLine(TREE_VLINE, curChildren , y + 1, x);
            move((y += curChildren), x);
            ++i;
        }
        wprintf(TREE_OUTBRANCH); 
        y += Tree_printFancy(       // printing outermost child
            Tree_childAt(self, i), y, x + OUTBRANCH_SIZE, print
        ) - 1;
    }   
    return y - descendants + 1;
}

It is applicable rather for console printing. Function move(y, x) moves cursor to (y, x) location on the screen. The best part is, you may change style of output by changing variables TREE_VLINE, TREE_INBRANCH, TREE_OUTBRANCH, length of two last strings doesn't matter. And you can print whatever you like, by passing Printer function pointer, which will print the value of the current tree node. Output looks like this

它更适用于控制台打印。函数的作用是:将光标移动到屏幕上的位置。最好的部分是，您可以通过改变变量TREE_VLINE、TREE_INBRANCH、TREE_OUTBRANCH来改变输出样式，最后两个字符串的长度并不重要。您可以通过传递打印机函数指针来打印任何您喜欢的内容，它将打印当前树节点的值。输出是这样的