如何以格式良好的方式打印一棵树？

Question

在树结构中打印树的最简单方法是什么？比如……

                  some root
              /     |         \
          child1   child2     child 3
           /
      anotherchild               / \
                             yup     another

即使是手动格式化也很难。如何让程序以这种方式打印一棵树？

Answer 1

除非有一些不错的图形库可供您使用，否则您将在以您描述的方式表示层次结构时遇到很多麻烦。

假设您想将其打印到控制台或文件，您将不得不预先计算整个树中所有数据元素的长度，以便将它们正确排列。你如何处理像换行这样的事情？

更好的方法是垂直表示树，使用缩进来显示子元素。

Root
    - Child1
        - Grandchild1
        - Grandchild2
    - Child2
        - Grandchild3
        - Grandchild4

这更容易编码，并且更能容忍换行之类的事情 - 因为一行上只有一个元素。这就是文件夹浏览器或 xml 文档显示其分层数据的方式。

为此，您需要进行深度优先遍历，并在递归步骤之前打印出节点：

public void PrintNode(TreeNode node)
{
    PrintNode(node, 0);
}

private void PrintNode(TreeNode node, int indentation)
{
    // Print the value to the console/file/whatever
    // This prefixes the value with the necessary amount of indentation
    Print(node.Value, indentation);

    // Recursively call the child nodes.
    foreach(TreeNode childNode in node.Children)
    {
        PrintNode(childNode, indentation + 1); // Increment the indentation counter.
    }
}

希望有帮助

Answer 2

以下答案是用 java 编写的，但它非常简单，可以轻松地转录为其他语言：

public interface Function1<R, T1>
{
    R invoke( T1 argument1 );
}

public interface Procedure1<T1>
{
    void invoke( T1 argument1 );
}

public static <T> void dump( T node, Function1<List<T>,T> breeder,
       Function1<String,T> stringizer, Procedure1<String> emitter )
{
    emitter.invoke( stringizer.invoke( node ) );
    dumpRecursive( node, "", breeder, stringizer, emitter );
}

private static final String[][] PREFIXES = { { " ├─ ", " │  " }, { " └─ ", "    " } };

private static <T> void dumpRecursive( T node, String parentPrefix,
        Function1<List<T>,T> breeder, Function1<String,T> stringizer,
        Procedure1<String> emitter )
{
    for( Iterator<T> iterator = breeder.invoke( node ).iterator(); iterator.hasNext(); )
    {
        T childNode = iterator.next();
        String[] prefixes = PREFIXES[iterator.hasNext()? 0 : 1];
        emitter.invoke( parentPrefix + prefixes[0] + stringizer.invoke( childNode ) );
        dumpRecursive( childNode, parentPrefix + prefixes[1], breeder, stringizer, emitter );
    }
}

它会产生以下输出：

Automobile
 ├─ Passenger Vehicle
 │   ├─ Light Passenger Vehicle
 │   │   ├─ Two Wheeled
 │   │   │   ├─ Moped
 │   │   │   ├─ Scooter
 │   │   │   └─ Motorcycle
 │   │   ├─ Three Wheeled
 │   │   └─ Four Wheeled
 │   │       ├─ Car
 │   │       ├─ Station Wagon
 │   │       ├─ Pick-up Truck
 │   │       └─ Sports Utility Vehicle
 │   └─ Heavy Passenger Vehicle
 │       ├─ Bus
 │       │   ├─ Single-Deck Bus
 │       │   │   ├─ Mini Bus
 │       │   │   └─ Big Bus
 │       │   └─ Double-Deck Bus
 │       └─ Coach
 │           ├─ Deluxe
 │           └─ Air-Conditioned
 └─ Goods Vehicle
     ├─ Light Goods Vehicle
     │   ├─ Delivery Van
     │   ├─ Light Truck
     │   └─ Tempo
     │       ├─ Three Wheeler Tempo
     │       └─ Four Wheeler Tempo
     └─ Heavy Goods Vehicle
         ├─ Truck
         └─ Tractor Trailer

...如果您使用以下示例程序调用它：

final class Scratch
{
    static class Node
    {
        String name;
        List<Node> children;

        Node( String name, Node... children )
        {
            this.name = name;
            this.children = Arrays.asList( children );
        }
    }

    public static void main( String[] args )
    {
        Node tree = new Node( "Automobile",
                new Node( "Passenger Vehicle",
                        new Node( "Light Passenger Vehicle",
                                new Node( "Two Wheeled",
                                        new Node( "Moped" ),
                                        new Node( "Scooter" ),
                                        new Node( "Motorcycle" ) ),
                                new Node( "Three Wheeled" ),
                                new Node( "Four Wheeled",
                                        new Node( "Car" ),
                                        new Node( "Station Wagon" ),
                                        new Node( "Pick-up Truck" ),
                                        new Node( "Sports Utility Vehicle" ) ) ),
                        new Node( "Heavy Passenger Vehicle",
                                new Node( "Bus",
                                        new Node( "Single-Deck Bus",
                                                new Node( "Mini Bus" ),
                                                new Node( "Big Bus" ) ),
                                        new Node( "Double-Deck Bus" ) ),
                                new Node( "Coach",
                                        new Node( "Deluxe" ),
                                        new Node( "Air-Conditioned" ) ) ) ),
                new Node( "Goods Vehicle",
                        new Node( "Light Goods Vehicle",
                                new Node( "Delivery Van" ),
                                new Node( "Light Truck" ),
                                new Node( "Tempo",
                                        new Node( "Three Wheeler Tempo" ),
                                        new Node( "Four Wheeler Tempo" ) ) ),
                        new Node( "Heavy Goods Vehicle",
                                new Node( "Truck" ),
                                new Node( "Tractor Trailer" ) ) ) );
        dump( tree, n -> n.children, n -> n.name, s -> System.out.println( s ) );
    }
}

Answer 3

好吧，你可以尝试类似 PHP 的 var_dump - 如果你在树状数组上尝试 var_dump，它会给你一个该树的公平表示，即：

root {
    child1 {
        anotherchild
    }
    child2
    child3 {
        yup
        another
    }
}

Answer 4

虽然我自己没有尝试过，graphviz 有一个纯文本输出格式。

Answer 5

对于类似问题，这个答案怎么样？ ？
它打印出一棵漂亮的 ASCII 艺术树。

或者如果您愿意的话，也许这个完全图形化吗？

Answer 6

去年我不得不这样做，编写一个家谱应用程序。在网上找到了一个java教程，它对我有帮助，但今天我的Google-fu失败了，所以我不得不简单地解释一下。

它只是一种基于子节点调整父节点位置的递归算法。在伪代码中，它是这样的：

positionNode (node,x,y) {
    foreach (child in node.children) {
        positionNode(child,x,y+1)
        x ++
    }
    node.x = (x-1)/2
    node.y = y
}

我可能没有正确记住这一点，您可能需要稍微调整代码才能使其正确。