Подтвердить что ты не робот

Как распечатать древовидную структуру?

Я пытаюсь улучшить производительность в нашем приложении. У меня есть информация о производительности в виде дерева вызовов со следующим классом 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 - я не могу просто использовать повторяющуюся строку для отступов узлов.

4b9b3361

ОТВЕТЫ

Ответ 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;
    }
}