我如何打印出树状结构?

我正在尝试提高我们应用程序的性能。 我以调用树的形式获得了性能信息,其中包含以下节点类:

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

Simon asked 2020-06-27T13:00:40Z
8个解决方案
79 votes

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

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
Will answered 2020-06-27T13:00:58Z
25 votes

递归

您需要跟踪缩进字符串,该缩进字符串在您深入到树中时会被修改。 为了避免添加额外的|个字符,您还需要知道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));
            }
        }
    }
}
Joshua Stachowski answered 2020-06-27T13:01:40Z
9 votes

创建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
Gacek answered 2020-06-27T13:02:08Z
6 votes

这是@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
Phrogz answered 2020-06-27T13:02:50Z
5 votes

我正在使用以下方法打印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>
KSC answered 2020-06-27T13:03:15Z
1 votes

这是Joshua Stachowski答案的通用版本。 关于Joshua Stachowski的回答的好处是,它不需要实际的节点类来实现任何其他方法,而且看起来也不错。

我使他的解决方案通用,可以用于任何类型而无需修改代码。

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

用法

 PrintTree(rootNode, x => x.ToString(), x => x.Children);
Amit Hasan answered 2020-06-27T13:03:45Z
0 votes

具有完全可选项而不使用递归的最佳方法是`[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;
    }
}
Tigran Vardanyan answered 2020-06-27T13:04:05Z
0 votes

使用(y,x)坐标

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

它适用于控制台打印。函数move(y,x)将光标移动到屏幕上的(y,x)位置。最好的部分是,您可以通过更改变量来更改输出样式TREE_VLINE,TREE_INBRANCH,TREE_OUTBRANCH,最后两个字符串的长度无关紧要。 然后,您可以通过传递打印机函数指针来打印任何所需内容,该指针将打印当前树节点的值。输出看起来像这样

Veetaha answered 2020-06-27T13:04:34Z
translate from https://stackoverflow.com:/questions/1649027/how-do-i-print-out-a-tree-structure