¿Cómo imprimo una estructura de árbol?

Estoy tratando de mejorar el rendimiento en nuestra aplicación. Tengo información de rendimiento en forma de un árbol de llamadas, con la siguiente clase de nodo:

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

Quiero imprimir el árbol de modo que pueda ver líneas entre los nodos, algo así como en esta pregunta . ¿Qué es un algoritmo que puedo usar en C # para hacer eso?

Editar: Obviamente necesito usar la recursión, pero mis bashs siguen poniendo las líneas en los lugares equivocados. Lo que estoy pidiendo es un algoritmo específico que imprima el árbol de una manera agradable: los detalles de cuándo imprimir una línea vertical y cuándo imprimir una horizontal.

Editar: no es suficiente usar copias de una cadena para sangrar los nodos. No estoy buscando

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

tiene que ser

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

o algo similar, siempre y cuando la estructura del árbol sea visible. Observe que C y D están sangrados de forma diferente a G – No puedo usar una cadena repetida para sangrar los nodos.

El truco es pasar una cuerda como sangrado y tratar especialmente al último niño:

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

Si se llama así:

 root.PrintPretty("", true); 

saldrá en este estilo:

 \-root \-child |-child \-child |-child |-child \-child |-child |-child | |-child | \-child | |-child | |-child | |-child | \-child | \-child | \-child \-child |-child |-child |-child | \-child \-child \-child 

Con recursión

Tendrá que hacer un seguimiento de una cadena de sangría que se modifica a medida que profundiza en el árbol. Para evitar agregar extra | personajes, también necesitarás saber si el Nodo es el último niño en ese conjunto.

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

Cuando se llama así:

 PrintTree(node, "", true) 

Producirá un texto como este:

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

Sin recursión

Si tiene un árbol muy profundo y el tamaño de la stack de llamadas es limitado, puede realizar un recorrido de árbol estático no recursivo para generar el mismo resultado:

 public static void PrintTree(Node tree) { List firstStack = new List(); firstStack.Add(tree); List> childListStack = new List>(); childListStack.Add(firstStack); while (childListStack.Count > 0) { List 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(tree.Children)); } } } } 

Crea el método PrintNode y usa la recursión:

 class Node { public string Name; public decimal Time; public List Children = new List(); 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 + " |"); } } 

Y a continuación, para imprimir todo el árbol, simplemente ejecuta:

 topNode.PrintNode(""); 

En mi ejemplo, nos daría algo como eso:

  + 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 

Aquí hay una variación de la respuesta (actualmente aceptada) de @Will. Los cambios son:

  1. Esto utiliza símbolos Unicode en lugar de ASCII para una apariencia más agradable.
  2. El elemento raíz no está sangrado.
  3. El último elemento secundario de un grupo tiene una línea ‘en blanco’ añadida después (hace que sea más fácil analizar visualmente).

Presentado como pseudo-código para un consumo más fácil fuera de 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, "" ) 

Resultado de la muestra:

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

Estoy usando el siguiente método para imprimir un BST

 private void print(Node root, String prefix) { if (root == null) { System.out.println(prefix + "+- "); return; } System.out.println(prefix + "+- " + root); print(root.left, prefix + "| "); print(root.right, prefix + "| "); } 

Lo siguiente es la salida.

 +- 43(l:0, d:1) | +- 32(l:1, d:3) | | +- 10(l:2, d:0) | | | +-  | | | +-  | | +- 40(l:2, d:2) | | | +-  | | | +- 41(l:3, d:0) | | | | +-  | | | | +-  | +- 75(l:1, d:5) | | +- 60(l:2, d:1) | | | +-  | | | +- 73(l:3, d:0) | | | | +-  | | | | +-  | | +- 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) | | | | | | | +-  | | | | | | | +-  | | | | | | +-  | | | | | +-  | | | | +-  | | | +-  

Esta es una versión genérica de la respuesta de Joshua Stachowski. Lo bueno de la respuesta de Joshua Stachowski es que no requiere que la clase de nodo real implemente ningún método adicional y se ve bien también.

Hice su solución genérica que se puede utilizar para cualquier tipo sin modificar el código.

  public static void PrintTree(T rootNode, Func nodeLabel, Func> childernOf) { var firstStack = new List(); firstStack.Add(rootNode); var childListStack = new List>(); childListStack.Add(firstStack); while (childListStack.Count > 0) { List 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(children)); } } } } 

Uso

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

La mejor manera con la opción completa sin recurrir es ` 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; } } 

Usar coordenadas (y, x)

Código C aquí:

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

Es aplicable más bien para la impresión de consola. El movimiento de función (y, x) mueve el cursor a la ubicación (y, x) en la pantalla. La mejor parte es que puede cambiar el estilo de salida cambiando las variables TREE_VLINE, TREE_INBRANCH, TREE_OUTBRANCH, la longitud de las dos últimas cadenas no importa. Y puede imprimir lo que quiera pasando el puntero de la función Impresora, que imprimirá el valor del nodo del árbol actual. La salida se ve así