trees to DOT graphs

treeviz.lhs

The binary tree datatype:

> data Tree = Leaf | Fork Tree Int Tree deriving Show                                     

A simple insert function implementing a Binary Search Tree:

> insert :: Int -> Tree -> Tree                                                           
> insert n Leaf = Fork Leaf n Leaf                                                        
> insert n (Fork l m r) | (n <= m)  = Fork (insert n l) m r                               
>                       | otherwise = Fork l m (insert n r)                               

Converting a list of integers into a tree:

> listToTree :: [Int] -> Tree                                                             
> listToTree = foldl (\t n -> insert n t) Leaf      

Convert the tree into a list of nodes and connections in graphviz DOT format:

> toDot'                :: Int -> Tree -> (Int, [String])                                 
> toDot' n Leaf         = (n+1, ["  " ++ show n ++ " [label=Leaf];"])                     
> toDot' n (Fork l m r) = (q, ls ++ rs ++ ms)                                             
>         where (p, ls) = toDot' (n+1) l;                                                 
>               (q, rs) = toDot' p r;                                                     
>                    ms = ["  " ++ show n ++ " [label=" ++ show m ++ "];"]                
>                      ++ ["  " ++ show n ++ " -> " ++ show (n+1) ++ ";"]                 
>                      ++ ["  " ++ show n ++ " -> " ++ show p ++ ";"] 

Add the header and footer to the list of nodes:

> toDot :: Tree -> String                                                                 
> toDot t = unlines $ ["digraph Tree {"] ++ snd(toDot' 0 t) ++ ["}"]    

Example:
> {-
> Main> putStr $ (toDot.listToTree) [9,5,12,3,7,10,13]
> digraph Tree {
>   3 [label=Leaf];
>   4 [label=Leaf];
>   2 [label=3];
>   2 -> 3;
>   2 -> 4;
>   6 [label=Leaf];
>   7 [label=Leaf];
>   5 [label=7];
>   5 -> 6;
>   5 -> 7;
>   1 [label=5];
>   1 -> 2;
>   1 -> 5;
>   10 [label=Leaf];
>   11 [label=Leaf];
>   9 [label=10];
>   9 -> 10;
>   9 -> 11;
>   13 [label=Leaf];
>   14 [label=Leaf];
>   12 [label=13];
>   12 -> 13;
>   12 -> 14;
>   8 [label=12];
>   8 -> 9;
>   8 -> 12;
>   0 [label=9];
>   0 -> 1;
>   0 -> 8;
> }
> -}

Use [shape=point] for the leaves. It will make the tree more pretty. Thanks!