C# 如何打印树结构？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1649027/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do I print out a tree structure?
提问by Simon
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 不同 - 我不能只使用重复的字符串来缩进节点。
采纳答案by Will
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
回答by Gacek
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
回答by Joshua Stachowski
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.
您需要跟踪在深入到树中时修改的缩进字符串。为了避免添加额外的|字符，您还需要知道 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);
}
}
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 verydeep 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));
}
}
}
}
回答by KSC
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>
回答by Phrogz
Here is a variation on the (currently-accepted) answer by @Will. The changes are:
这是@Will 的（当前接受的）答案的变体。变化是：
- This uses Unicode symbols instead of ASCII for a more pleasing appearance.
- The root element is not indented.
- The last child of a group has a 'blank' line added after it (makes it easier to visually parse).
- 这使用 Unicode 符号而不是 ASCII 以获得更令人愉悦的外观。
- 根元素不缩进。
- 组的最后一个子级在其后面添加了一个“空白”行（使其更易于视觉解析）。
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
回答by Amit Hasan
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);
回答by Tigran Vardanyan
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;
}
}
回答by Veetaha
Using (y, x) coordinates
使用 (y, x) 坐标
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
它更适用于控制台打印。函数 move(y, x) 将光标移动到屏幕上的 (y, x) 位置。最好的部分是，您可以通过更改变量 TREE_VLINE、TREE_INBRANCH、TREE_OUTBRANCH 来更改输出样式，最后两个字符串的长度无关紧要。你可以打印任何你喜欢的东西，通过传递打印机函数指针，这将打印当前树节点的值。输出看起来像这样
