Как вы можете распечатать дерево красиво отформатированным способом?

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

Я должен был сделать это в прошлом году, написав приложение к генеалогическому дереву. Нашел онлайн-учебник по Java, который помог, но мой Google-фу не помог мне сегодня, поэтому мне придется просто объяснить это.

Это просто рекурсивный алгоритм, который регулирует положение родительского узла на основе дочерних узлов. В псевдокоде это примерно так:

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

Возможно, я не помню это правильно, возможно, вам придется немного подправить код, чтобы сделать его правильным.

Answer 4

Как насчет этого ответа на аналогичный вопрос? Печатает красивое дерево ASCII-art.

Или, может быть, этот , если вы хотите использовать полностью графическое изображение?

Answer 5

Хотя я сам не пробовал, graphviz имеет простой текст формат вывода .

Answer 6

Ну, вы можете попробовать что-то вроде PHP var_dump - если вы попробуете var_dump на древовидном массиве, он даст вам правильное представление этого дерева, а именно:

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