OCaml: draw binary trees

Question

I am working on some programs using trees. I was wondering if there is any piece of code to draw general trees in OCaml.

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

All I find on internet uses Caml Light, not Objective Caml.
Thanks in advance.

Answer 1

Could you clarify what you mean by "draw"? I assume you're thinking of a graphical visualization of the tree?

I have had reasonably good experience with generating graph/tree descriptions in the dot format, used by the tool graphviz. The idea is that your OCaml program generates a textual representation of the graph in this format, then you use external tools to render it (turn it into an image), and possibly display it on the screen.

Dot works for general graphs. While you may find specialized tools for binary trees that have more features, in my experience it works rather well with all kind of trees and display something that is usually what you'd like. Now the tool is not without its flaws, and I've hit bugs (calling dot segfaults) in some cases. Still I think that's a reasonable choice.

How to output in dot format concretely: pick any example of already-existing graph, the structure will be quite obvious : it is only a textual format. Then you write your code running over the graph structure, calling Printf with the right stuff for labels, etc., and voila. For example, this example looks good, and here is the source format. I quote the relevant part:

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

It is usually very easy and funny to use the Graphics library to draw your tree, if it is simple and not too deep.

If you want a textual representation:

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