Как распечатать древовидную структуру?
Я пытаюсь улучшить производительность в нашем приложении. У меня есть информация о производительности в виде дерева вызовов со следующим классом node:
public class Node
{
public string Name; // method name
public decimal Time; // time spent in method
public List<Node> Children;
}
Я хочу распечатать дерево, чтобы я мог видеть строки между узлами - что-то вроде этого вопроса. Какой алгоритм я могу использовать в С# для этого?
Изменить: Очевидно, мне нужно использовать рекурсию, но мои попытки продолжают помещать строки в неправильные места. То, что я прошу, - это конкретный алгоритм, который будет красиво печатать дерево - подробности о том, когда печатать вертикальную линию и когда печатать горизонтальную.
Изменить: Недостаточно просто использовать копии строки для отступов узлов. Я не ищу
A
|-B
|-|-C
|-|-D
|-|-|-E
|-F
|-|-G
он должен быть
A
+-B
| +-C
| +-D
| +-E
+-F
+-G
или что-нибудь подобное, если видна древовидная структура. Обратите внимание, что C и D имеют разные отличия от G - я не могу просто использовать повторяющуюся строку для отступов узлов.
Ответы
Ответ 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
Ответ 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));
}
}
}
}
Ответ 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
Ответ 4
Я использую следующий метод для печати 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>
Ответ 5
Ниже приведен вариант ответа (в настоящее время) на @Will. Изменения:
- Это использует символы Unicode вместо ASCII для более приятного внешнего вида.
- Корневой элемент не имеет отступов.
- У последнего дочернего элемента группы после него добавлена "пустая" строка (упрощается визуальный анализ).
Представлен как псевдокод для более легкого использования за пределами С++:
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
Ответ 6
Это общая версия ответа Джошуа Стаховски. Хорошая вещь о ответе Джошуа Стаховски заключается в том, что он не требует, чтобы класс node реализовал какой-либо дополнительный метод, и он тоже выглядит хорошо.
Я сделал свое решение generic, которое можно использовать для любого типа без изменения кода.
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);
Ответ 7
Лучший способ с полной возможностью без использования рекурсии - это `
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;
}
}
