Làm thế nào bạn có thể in ra một cây theo cách được định dạng độc đáo?

Question

Cách dễ nhất để in ra một cái cây trong cấu trúc cây của nó là gì? Chẳng hạn như ...

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

Thậm chí việc định dạng bằng tay cũng khó. Làm thế nào bạn có thể làm cho một chương trình in một cây theo cách này?

Answer 1

Vâng, bạn có thể thử một cái gì đó giống như var_dump PHP - nếu bạn cố gắng var_dump trên một mảng cây giống, nó sẽ cung cấp cho bạn một đại diện hợp lý của cây, đó là:

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

Answer 2

Mặc dù tôi đã không' t tự mình thử, graphviz có văn bản thuần túy output format.

Answer 3

Trừ khi có một số thư viện đồ họa đẹp mà bạn có thể sử dụng, bạn sẽ gặp nhiều rắc rối thể hiện cấu trúc phân cấp theo cách bạn mô tả.

Giả sử bạn muốn in nó vào Console hoặc tệp, bạn sẽ phải tính toán trước độ dài của tất cả các phần tử dữ liệu trong toàn bộ cây để xếp chúng chính xác. Và làm thế nào để bạn xử lý những thứ như line-wrap?

Cách tốt hơn là đại diện cho cây theo chiều dọc, sử dụng thụt lề để hiển thị phần tử con.

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

Điều này đơn giản hơn nhiều để mã và khoan dung hơn những thứ như linewrap - vì chỉ có một phần tử trên một dòng. Đây là cách trình duyệt thư mục hoặc tài liệu xml có thể hiển thị dữ liệu phân cấp của nó.

Để làm theo cách này, bạn làm một traversal sâu-đầu tiên và trước khi bước đệ quy bạn in ra các nút:

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

Hy vọng rằng sẽ giúp

Answer 4

Làm thế nào về this answer cho một câu hỏi tương tự? Nó in một cây ASCII-nghệ thuật đẹp.

Hoặc có thể this one nếu bạn muốn đồ họa đầy đủ?

Answer 5

Tôi phải làm điều này năm ngoái bằng cách viết một ứng dụng cây gia đình. Tìm thấy một hướng dẫn trực tuyến java đã giúp nhưng Google-fu của tôi không thành công cho tôi ngày hôm nay vì vậy tôi sẽ phải chỉ đơn giản là giải thích nó.

Nó chỉ đơn giản là một thuật toán đệ quy điều chỉnh vị trí của nút cha dựa trên các nút con. Trong mã giả nó là một cái gì đó như thế này:

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

Tôi có thể không nhớ chính xác, bạn có thể cần phải chỉnh sửa mã một chút để làm cho nó đúng.

Answer 6

Câu trả lời sau đây là trong java, nhưng nó là đơn giản như vậy mà nó có thể dễ dàng sao chép sang các ngôn ngữ khác:

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

Nó tạo ra kết quả như sau:

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 

...nếu bạn gọi nó bằng cách sử dụng chương trình mẫu sau đây:

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