OCaml: vẽ cây nhị phân

Question

Tôi đang làm việc trên một số chương trình sử dụng cây cối. Tôi đã tự hỏi nếu có bất kỳ đoạn mã nào để vẽ cây chung trong OCaml.

type Tree = Node of Tree * int * Tree | Child of int;; 

Tất cả những gì tôi tìm thấy trên internet đều sử dụng Caml Light, không phải Camlive mục tiêu.
Cảm ơn bạn trước.

Answer 1

Bạn có thể làm rõ ý bạn bằng cách "vẽ" không? Tôi cho rằng bạn đang nghĩ đến hình ảnh đồ họa của cây?

Tôi đã có trải nghiệm hợp lý tốt với việc tạo mô tả biểu đồ/cây ở định dạng dấu chấm, được sử dụng bởi công cụ graphviz. Ý tưởng là chương trình OCaml của bạn tạo ra một biểu diễn văn bản của biểu đồ ở định dạng này, sau đó bạn sử dụng các công cụ bên ngoài để hiển thị nó (biến nó thành hình ảnh) và có thể hiển thị nó trên màn hình.

Chấm hoạt động cho đồ thị chung. Mặc dù bạn có thể tìm thấy các công cụ chuyên biệt cho cây nhị phân có nhiều tính năng hơn, theo kinh nghiệm của tôi, nó hoạt động khá tốt với tất cả các loại cây và hiển thị thứ gì đó thường là thứ bạn muốn. Bây giờ công cụ không phải là không có sai sót của nó, và tôi đã nhấn lỗi (gọi dot segfaults) trong một số trường hợp. Tôi vẫn nghĩ đó là một lựa chọn hợp lý.

Cách xuất ở định dạng dot cụ thể: chọn bất kỳ example biểu đồ đã tồn tại nào, cấu trúc sẽ khá rõ ràng: đó chỉ là định dạng văn bản. Sau đó, bạn viết mã của mình chạy qua cấu trúc biểu đồ, gọi số Printf với nội dung phù hợp cho nhãn, v.v. và thì đấy. Ví dụ: this example có vẻ tốt và here là định dạng nguồn. Tôi xin trích dẫn một phần có liên quan:

/* courtesy Ian Darwin and Geoff Collyer, Softquad Inc. */ 
digraph unix { 
    size="6,6"; 
    node [color=lightblue2, style=filled]; 
    "5th Edition" -> "6th Edition"; 
    "5th Edition" -> "PWB 1.0"; 
    "6th Edition" -> "LSX"; 
    "6th Edition" -> "Interdata"; 
    "Interdata" -> "Unix/TS 3.0"; 
    "Interdata" -> "PWB 2.0"; 
    "Interdata" -> "7th Edition"; 
    "7th Edition" -> "8th Edition"; 
    "7th Edition" -> "32V"; 
    "7th Edition" -> "V7M"; 
    "V7M" -> "Ultrix-11"; 
    "8th Edition" -> "9th Edition"; 
    [...] 
} 

Answer 2

Nó thường là rất dễ dàng và vui nhộn để sử dụng thư viện Graphics để vẽ cây của bạn, nếu nó là đơn giản và không quá sâu.

Nếu bạn muốn có một đại diện văn bản:

type tree = Node of tree * int * tree | Child of int;; 
let draw tree = 
    let rec print indent tree = 
    match tree with 
     Child n -> 
     Printf.printf "%s%d\n" indent n 
    | Node (left, n, right) -> 
     Printf.printf "%s----\n" indent; 
     print (indent^"| ") left; 
     Printf.printf "%s%d\n" indent n; 
     print (indent^"| ") right; 
     Printf.printf "%s----\n" indent 
    in 
    print "" tree