OCaml: rysuj drzewa binarne

Question

Pracuję nad niektórymi programami wykorzystującymi drzewa. Zastanawiałem się, czy istnieje jakiś fragment kodu do generowania drzewek w OCaml.

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

Wszystko, co znalazłem w Internecie, używa Caml Light, a nie Objective Caml.
Z góry dziękuję.

Answer 1

Czy możesz wyjaśnić, co masz na myśli przez "draw"? Zakładam, że myślisz o graficznej wizualizacji drzewa?

Mam dość dobre doświadczenia z generowaniem opisów wykresów/drzew w formacie punktowym, używanym przez narzędzie graphviz. Chodzi o to, że twój program OCaml generuje tekstową reprezentację wykresu w tym formacie, a następnie używa zewnętrznych narzędzi do renderowania (przekształcania go w obraz) i ewentualnie wyświetlania go na ekranie.

Dot działa dla ogólnych wykresów. Chociaż możesz znaleźć specjalistyczne narzędzia do drzewek binarnych, które mają więcej funkcji, z mojego doświadczenia wynika, że ​​działa całkiem dobrze ze wszystkimi rodzajami drzew i wyświetla coś, co zwykle jest tym, czego potrzebujesz. Teraz narzędzie nie jest pozbawione wad i trafiłem w kilka błędów (wywołując dot segfaults). Wciąż myślę, że to rozsądny wybór.

Sposób wyprowadzania w formacie dot konkretnie: wybierz dowolny example z już istniejącego wykresu, struktura będzie dość oczywista: jest to tylko format tekstowy. Następnie piszesz swój kod na strukturze wykresu, wywołując Printf z właściwymi materiałami na etykiety itp. I voila. Na przykład: this example wygląda dobrze, a here jest formatem źródłowym. Cytuję odpowiedni fragment:

/* 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

zazwyczaj jest bardzo łatwe i zabawne do korzystania z biblioteki Graphics narysować drzewo, jeśli to jest proste i nie jest zbyt głęboka.

Jeśli chcesz tekstową reprezentację:

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