How to draw a tree structure? (A two-dimensional space allocation tree recursion algorithm?)

Question

I have an arbitrary tree structure of nodes. I want to draw this tree to provide users a visual representation. I need to recurse over the tree and for each node add a graphic item to a list, and then just draw the list of items once tree recursion has finished. The recursion and drawing of items is of course trivial - what's a bit more complicated is how to position the graphic nodes so they do not overlap with other branches.

I'm using Android but that is not important - I'm looking for an approach, possibly an algorithm that can maintain a picture of 2D space as it passes over the tree so it just allocates the most appropriate coordinates for each node as it makes the pass.

Any ideas?

Update

This is the article with the best and most complete algorithm.

Answer 1

I would try the Walker algorithm. Here's an academic paper on the algorithm. If you want code to look at, look at the NodeLinkTreeLayout in Prefuse. Prefuse is open source so there shouldn't be any problems adapting the code to your situation as long as you follow the terms of the license.

Answer 2

I suggest drawing the tree linewise. You do this by using some kind of moving "drawing cursor".

You could store an attribute width for each node which is calculated as follows:

• the width of a leave is 1
• the width of an inner node is the sum of all childrens' widths

Then, you draw the root "in the first line" in the middle, which means, you just take root's width's half.

Then, you generate a grid over the image such that each gridline corresponds to one line resp. one step from left to right and each intersection of grid lines can contain a node and each node has enough space.

Then, you iterate through the childs and while iterating, you accumulate the children's widths and draw the children "in the next line". To draw currentChild, you move your drawing cursor currentWidth/2 to the right, draw currentChild, and move the drawing cursor the remaining currentWidth/2 to the right.

In order to get the nodes in a good order, you might consider a breadth first search.

I hope my explanation is clear, but I think it will be better, if I draw a little picture.

This is our tree (x are nodes, everything else edges)

   +-------x--+-------+
   |          |       |
 +-x-+     +-+x+-+  +-x-+
 |   |     | | | |  | | |
 x   x     x x x x  x x x

So, you calculate the leaf's widths:

   +-------x--+-------+
   |          |       |
 +-x-+     +-+x+-+  +-x-+
 |   |     | | | |  | | |
 1   1     1 1 1 1  1 1 1

Then, bottom up, the widths as sums of childrens' widths:

   +-------9--+-------+
   |          |       |
 +-2-+     +-+4+-+  +-3-+
 |   |     | | | |  | | |
 1   1     1 1 1 1  1 1 1

So, you start at the root (width 9) and go 4.5 steps to the rigt in the first line.

Then, you move your "drawing cursor" to the second line, "column 0" (go to left).

The first child has width 2, so we go 2/2=1 grid lines to the right and draw the node and move the drawing cursor the remaining 1 grid lines to the right in order to finish the node. So, the next node has width 4, which means, that we go right 4/2=2 grid lines, draw, go the remaining 2 steps, and so on.

And so on with the next line. At the end (or in intermediate steps), connect the nodes.

This procedure ensures that there are no overlapping nodes (if grid lines are far enough from each other), but it might lead to quite large tree diagrams that could use the space more efficiently.

In order to detect unused space, one might just scan the lines after the above process and look if there are unused grid line intersections and then possibly realign some nodes in order to fill space.