OCaml: рисовать бинарные деревья - PullRequest
Новая
       16

OCaml: рисовать бинарные деревья

9 голосов
/ 04 марта 2012

Я работаю над некоторыми программами, использующими деревья.Мне было интересно, есть ли какой-нибудь фрагмент кода для рисования общих деревьев в OCaml. 

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

Все, что я нахожу в Интернете, использует Caml Light, а не Objective Caml.
Заранее спасибо.

Ответы [ 2 ]

12 голосов
/ 04 марта 2012

Не могли бы вы уточнить, что вы подразумеваете под "рисовать"?Я предполагаю, что вы думаете о графической визуализации дерева?

У меня был достаточно хороший опыт создания описаний графиков / деревьев в формате точек, используемых инструментом graphviz .Идея состоит в том, что ваша программа OCaml генерирует текстовое представление графика в этом формате, затем вы используете внешние инструменты для его рендеринга (превращения в изображение) и, возможно, отображения его на экране.

Точка работаетдля общих графиков.Хотя вы можете найти специализированные инструменты для бинарных деревьев, которые имеют больше функций, по моему опыту, он довольно хорошо работает со всеми видами деревьев и отображает то, что обычно вам нравится.Теперь инструмент не лишен недостатков, и в некоторых случаях я сталкивался с ошибками (вызывая dot segfaults).Тем не менее, я думаю, что это разумный выбор.

Как выводить в формате dot конкретно: выбрать любой пример уже существующего графа, структура будет совершенно очевидна: это всего лишьтекстовый формат.Затем вы пишете свой код, работающий над структурой графа, вызывая Printf с нужным материалом для меток и т. Д., И вуаля.Например, этот пример выглядит хорошо, а здесь - исходный формат.Я цитирую соответствующую часть: 

/* 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";
    [...]
}
10 голосов
/ 04 марта 2012

Обычно очень просто и забавно использовать библиотеку Graphics для рисования вашего дерева, если оно простое и не слишком глубокое.

Если вы хотите текстовое представление: 

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