如何打印出树状结构?

我正在努力提高我们的应用程序的性能。 我有一个调用树的forms的性能信息,具有以下节点类:

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

我想打印出树,这样我可以看到节点之间的线 – 就像这个问题 。 我可以在C#中使用的algorithm是什么?

编辑:显然我需要使用recursion – 但我的尝试不断把行放在错误的地方。 我所要求的是一个特定的algorithm,它将以一种很好的方式打印树 – 何时打印垂直线以及何时打印水平线的细节。

编辑:仅使用string的副本缩进节点是不够的。 我不是在找

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

它一定要是

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

或类似的东西,只要树结构是可见的。 注意C和D的缩进方式与G不同 – 我不能只使用重复的string缩进节点。

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

 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 

如果你碰巧有一个非常深的树,并且你的调用堆栈大小是有限的,你可以做一个静态的,非recursion的树遍历,如下所示:

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

哪个会输出这样的东西:

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

创buildPrintNode方法并使用recursion:

 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 

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

这是@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 

这是Joshua Stachowski的答案的通用版本。 Joshua Stachowski的答案是,它不需要实际的节点类来实现任何额外的方法,它看起来也很好。

我提出了他的解决scheme通用的,可以用于任何types而无需修改代码。

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

没有使用recursion的完整选项的最好方法是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; } }