Pretty print a tree

Princess_40516 0
Viewed 10640

Let's say I have a binary tree data structure defined as follows

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

I have an instance of a tree as follows:

let x =
  Node
    (Node (Node (Nil,35,Node (Nil,40,Nil)),48,Node (Nil,52,Node (Nil,53,Nil))),
     80,Node (Node (Nil,82,Node (Nil,83,Nil)),92,Node (Nil,98,Nil)))

I'm trying to pretty-print the tree into something easy to interpret. Preferably, I'd like to print the tree in a console window like this:

        _______ 80 _______
       /                  \
    _ 48 _              _ 92 _
   /      \            /      \
 35       52         82       98
   \       \        /
    40      53    83

What's an easy way to get my tree to output in that format?

pretty-print f#
5 Answers

This is an intuition, I'm sure someone like Knuth had the idea, I'm too lazy to check.

If you look at your tree as an one dimensional structure you will get an array (or vector) of length L This is easy to build with an "in order" recursive tree traversal: left,root,right some calculations must be done to fill the gaps when the tree is unbalanced

2 dimension

                    _______ 80 _______
                   /                  \
                _ 48 _              _ 92 _
               /      \            /      \
             35       52         82       98
               \       \        /
                40      53    83

1 dimension :

             35 40 48   52 53 80 83 82    92    98   
           0 1  2  3  4  5  6  7  8  9 10 11 12 13 14

The pretty printed tree can be build using this array (maybe with something recursive) first using values at L/2 position, the X position is the L/2 value * the default length (here it is 2 characters)

                              80
    
    then (L/2) - (L/4)  and  (L/2) + (L/4) 
    
                   48                    92
    then L/2-L/4-L/8, L/2-L/4+L/8, L/2+L/4-L/8 and L/2+L/4+L/8 
    
              35        52         82          98
    
    ...

Adding pretty branches will cause more positional arithmetics but it's trivial here

You can concatenate values in a string instead using an array, concatenation will de facto calculate the best X postion and will allow different value size, making a more compact tree. In this case you will have to count the words in the string to extract the values. ex: for the first element using the L/2th word of the string instead of the L/2 element of the array. The X position in the string is the same in the tree.

N 35 40 48 N 52 53 80 83 82 N 92 N 98 N 
                   80
        48                    92
  35         52          82        98
     40         53    83
user_5746890
Related