如何打印树形结构？

Question

如何打印树形结构？

59

我正在尝试提高我们应用程序的性能。我以调用树的形式获得了性能信息，其中包含以下节点类：

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

我想打印出树形结构，以便我可以在节点之间看到连线 - 就像这个问题中的例子一样。我应该使用什么算法来在C#中完成这个任务？

编辑：显然我需要使用递归 - 但是我的尝试总是把线条放在错误的位置。我要求的是一种特定的算法，可以以良好的方式打印树形结构 - 包括何时打印垂直线和水平线的细节。

编辑：仅仅使用字符串的副本来缩进节点是不够的。我不是在寻找...

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

它必须是这样的

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

或类似的东西，只要树形结构是可见的。请注意，C和D的缩进方式与G - I不同 - 我不能只使用重复的字符串来缩进节点。

- Simon

以下是一些关于打印二叉树的其他答案，这将有助于未来访问此问题的访客：https://dev59.com/K2445IYBdhLWcg3wQX6G。其中特别有用的是水平打印树的答案。 - Ehtesh Choudhury

https://vanya.jp.net/vtree/ - humble_wolf

8个回答

41

使用递归

您需要跟踪一个缩进字符串，随着您深入树形结构，该字符串会被修改。为了避免添加额外的|字符，您还需要知道该节点是否是该集合中的最后一个子节点。

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

- Joshua Stachowski

1

非常好和优雅。我从你的答案中制作了一个通用版本。 - Amit Hasan

14

创建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

- Gacek

那并不会画出树的形状，它只是使用“|——”的副本进行缩进。我希望能够看到树的形状，所以算法必须留下间隙。 - Simon

抱歉，我不明白你在说什么。它做了与你给出的示例类似的事情。你想要实现什么？有哪些“差距”？ - Gacek

好的，我给你另一个例子。我写的只是主要概念，请自己多思考一下并将其应用于你的目的。这个想法是相同的，但你需要想出一个好的，“聪明”的使用方式。祝你好运！ - Gacek

所以你需要添加一些例程，为你格式化前缀字符串。试着玩一下，我相信它会起作用的。 - Gacek

简化一下 - 只需去掉那些不再继续的管道符号。这就是让我特别困惑的部分。 - Simon

我又编辑了代码。它更接近（虽然不完全符合你的需求，但是朝着正确的方向）。 - Gacek

10

这是对@Will目前被接受的答案的改进版。更改内容如下：

使用Unicode符号而不是ASCII，外观更美观。
根元素不缩进。
组的最后一个子元素后面添加了一行“空白”（使其更容易视觉解析）。

为了更方便地在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, "" )

样例结果：

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

- Phrogz

8

我使用以下方法打印二叉搜索树：

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>

- KSC

1

在二叉搜索树方面，@KSC的方法非常好，对我来说是最好的方法。我将只留下null的输出。 - David H.

3

这是 Joshua Stachowski 的答案的通用版本。Joshua Stachowski 的答案好在不需要实际的节点类实现任何额外的方法，而且看起来也很好。

我将他的解决方案改成了通用型，可以用于任何类型而无需修改代码。

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

- Amit Hasan

0

使用 (y, x) 坐标

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

它更适用于控制台打印。函数move(y, x)将光标移动到屏幕上的(y, x)位置。最好的部分是，您可以通过更改变量TREE_VLINE、TREE_INBRANCH、TREE_OUTBRANCH和两个最后一个字符串的长度来更改输出样式。并且您可以通过传递Printer函数指针来打印任何您喜欢的内容，该指针将打印当前树节点的值。输出看起来像this

- Veetaha

0

最佳方法是使用完整的选项，而不使用递归，具体请参考以下链接： 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;
    }
}

- Tigran Vardanyan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Will · Accepted Answer

诀窍是将字符串作为缩进传递，并特别对待最后一个子元素：

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