Thuật toán hình ảnh hóa cây

Question

Có một số thuật toán để hiển thị cấu trúc dữ liệu cây không? Tôi đã thử googling, nhưng couldnt tìm thấy bất kỳ. Tôi khá chắc chắn phải có một số thuật toán cho điều này không phải là nhiệm vụ đơn giản. Hoặc bất cứ ai có một số ý tưởng?

Answer 1

Giả sử: bạn muốn mỗi nút được hiển thị sao cho nút đó được đặt ở giữa các nút con của nó. Để đạt được điều này, tính toán chiều rộng của mỗi nút, mà tôi xác định là số lượng không gian ngang cần thiết để hiển thị toàn bộ cây con của nút này, sao cho nó không trùng lặp với các nhánh phụ của anh chị em trái hoặc phải của nó.

Điều này dẫn đến:

width = 1 + sum(widths of children's nodes) 

Vì vậy, làm một traversal sâu-đầu tiên thông qua cây để tính chiều rộng của mỗi nút. Để hiển thị, hãy thực hiện giao thoa lần đầu tiên để vẽ mức cây theo cấp độ.

Đây là ý tưởng sơ bộ về cách thực hiện. Bạn có thể muốn tinh chỉnh tính toán chiều rộng tùy thuộc vào chi tiết về cách bạn muốn hiển thị cây.

Answer 2

Bạn có thể sử dụng ngôn ngữ DOT với graphviz chẳng hạn.

Answer 3

Tree-mapping có lẽ là những gì bạn đang tìm kiếm. Graphviz là tốt cho hình dung các cấu trúc đồ thị không chuyên cho cấu trúc cây. Tôi không thể tìm thấy nó một lần nữa nhưng tôi nhớ đã đọc trong một bài báo khoa học rằng cây treemaps (tôi nghĩ voronoi) là tối ưu để đại diện cho cấu trúc cây, liên quan đến nơi chúng tiêu thụ và khu vực có thể được sử dụng để đại diện cho một số đơn vị (như kích thước byte cho thí dụ).

Here là một số lựa chọn thay thế.

Here là danh sách các bài viết hay và thông tin khác về chủ đề.

Answer 4

Bạn cũng có thể in cây từ trái sang phải, tức là gốc ở bên trái, cấp độ đầu tiên bên phải, v.v. Bạn sẽ tìm thấy cây được in với mỗi cấp trên 'cột' riêng của nó. Thuật toán có phần như sau:

print(node, spaces): 
    if node has left child: 
     print(left_child, spaces + ' ') 
    print spaces + node + '\n' 
    if node has right child: 
     print(right_child, spaces + ' ') 

Thuật toán này sẽ in một nút cây trên mỗi dòng. Mỗi cấp độ của cây sẽ được thụt vào bên phải bởi một số không gian. Thuật toán này sẽ in các mục theo thứ tự tăng dần, nhưng thứ tự giảm dần có thể đạt được bằng cách xử lý đúng con đầu tiên.