Comment imprimer une structure arborescente?
j'essaie d'améliorer les performances de notre application. J'ai des informations de performance sous la forme d'un arbre d'appels, avec la classe de noeuds suivante:
public class Node
{
public string Name; // method name
public decimal Time; // time spent in method
public List<Node> Children;
}
je veux imprimer l'arbre de sorte que je puisse voir les lignes entre les noeuds - quelque chose comme dans cette question . Qu'est-ce qu'un algorithme que je peux utiliser dans C# pour faire ça?
Edit: évidemment je dois utiliser la récursion - mais mes tentatives continuent à mettre les lignes dans les mauvais endroits. Ce que je demande, c'est un algorithme spécifique qui va imprimer l'arbre dans une belle manière - le moment d'imprimer une ligne verticale et lors de l'impression d'une horizontale.
Edit: il ne suffit pas d'utiliser des copies d'une chaîne pour indenter les noeuds. Je ne cherche pas
A
|-B
|-|-C
|-|-D
|-|-|-E
|-F
|-|-G
il a à être
A
+-B
| +-C
| +-D
| +-E
+-F
+-G
ou quelque chose de similaire, tant que la structure de l'arbre est visible. Notez que C et D sont indenté différemment de G-Je ne peux pas utiliser une chaîne répétée pour indenter les noeuds.
8 réponses
le truc est de passer une corde comme le tiret et de traiter le dernier enfant spécialement:
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 on l'appelle ainsi:
root.PrintPretty("", true);
sortira dans ce 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
Avec Récursion
vous aurez besoin de garder la trace d'une chaîne d'indentation qui est modifié alors que vous allez plus profondément dans l'arbre. Pour éviter d'ajouter des caractères supplémentaires | , vous aurez également besoin de savoir si le noeud est le dernier enfant dans cet ensemble.
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);
}
}
quand on l'appelle ainsi:
PrintTree(node, "", true)
il va sortir le texte comme ceci:
+- 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
Sans Récursion
si vous avez un très arbre profond et que la taille de votre pile d'appels est limitée, vous pouvez à la place faire une traversée d'arbre statique, non-récursive pour produire le même résultat:
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));
}
}
}
}
Créer PrintNode méthode et l'utilisation de la récursivité:
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 + " |");
}
}
et ensuite pour imprimer l'arbre entier il suffit d'exécuter:
topNode.PrintNode("");
Dans mon exemple, il nous donnerait quelque chose comme:
+ 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
voici une variation de la réponse (actuellement acceptée) de @Will. Les modifications sont les suivantes:
- cela utilise des symboles Unicode au lieu de ASCII pour une apparence plus agréable.
- l'élément racine n'est pas indenté.
- le dernier enfant d'un groupe est suivi d'une ligne "blanche" (ce qui facilite l'analyse visuelle).
présenté sous forme de pseudo-code pour une consommation plus facile en dehors 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, "" )
résultat de L'échantillon:
Body
├╴PaintBlack
├╴CarPaint
├╴Black_Material
├╴PaintBlue
├╴Logo
│ └╴Image
│
├╴Chrome
├╴Plastic
├╴Aluminum
│ └╴Image
│
└╴FabricDark
j'utilise la méthode suivante pour imprimer un 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 + "| ");
}
suivant est le résultat.
+- 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>
C'est une version générique de la réponse de Joshua Stachowski. La bonne chose à propos de la réponse de Joshua Stachowski est qu'il ne nécessite pas la classe de noeud réelle pour mettre en œuvre toute méthode supplémentaire et il semble agréable ainsi.
j'ai fait sa solution générique qui peut être utilisé pour n'importe quel type sans modifier le 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));
}
}
}
}
Utilisation
PrintTree(rootNode, x => x.ToString(), x => x.Children);
la meilleure façon avec l'optionalité complète sans utiliser la récursion est" 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;
}
}
en utilisant les coordonnées (y, x)
code C ici:
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;
}
s'applique plutôt à l'impression sur console. Déplacement de la fonction (y, x) déplace le curseur à (y, x) l'emplacement sur l'écran. La meilleure partie est, vous pouvez changer le style de sortie en changeant les variables TREE_VLINE, TREE_INBRANCH, TREE_OUTBRANCH, la longueur des deux dernières chaînes n'a pas d'importance. Et vous pouvez imprimer ce que vous voulez, en passant le pointeur de fonction D'imprimante, qui imprimera la valeur de actuel nœud de l'arborescence. Sortie ressemble à ce
