How to draw a tree structure? (Algorithm for a recursive spatial distribution tree?)

Question

I have an arbitrary tree structure of nodes. I want to draw this tree to provide users with a visual representation. I need to rewrite the tree and add a graphic element to the list for each node, and then just draw a list of elements after the tree recursion is complete. Recursion and drawing elements, of course, are trivial - which is somewhat more complicated, is the arrangement of graphic nodes so that they do not overlap with other branches.

I use Android, but it doesn’t matter. I'm looking for an approach, perhaps an algorithm that can support an image of 2D space as it moves through the tree, so it just highlights the most suitable coordinates for each node, as it makes a pass.

Any ideas?

Update

This article is with the best and most complete algorithm.

Answer 1

I would try Walker's algorithm. Here is an academic article on the algorithm. If you want the code to look, check out NodeLinkTreeLayout in Prefuse . Prefuse is open source, so there should be no problem adapting the code to your situation if you comply with the license terms.

Answer 2

I suggest drawing a tree line. You do this using some kind of moving "drawing cursor".

You can save the width attribute for each node, which is calculated as follows:

• vacation width - 1
• width inner node is the sum of all width s of children

Then you draw the root “in the first line” in the middle, which means that you just shorten the width half.

Then you create a grid above the image, so that each grid line corresponds to one line, respectively. one step from left to right, and each intersection of the grid lines can contain a node, and each node has enough space.

Then you iterate over the children and, iterate over, you accumulate the children width and draw the children "in the next line." To draw currentChild , you move the draw cursor currentWidth/2 to the right, draw currentChild and move the draw cursor to the remaining currentWidth/2 to the right.

To get the nodes in good order, you can consider the first width search.

I hope my explanations are clear, but I think it would be better if I draw a little.

This is our tree ( x - nodes, all other edges)

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

So you compute sheet width s:

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

Then, from bottom to top, width as the sum of the child width s:

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

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

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

The first child has a width 2, so we will direct the grid lines 2/2 2/2=1 the right and draw a node and move the drawing cursor to the remaining 1 grid lines to the right to end the node. So, the next node has a width 4, which means we go right 4/2 = 2 grid lines, draw, go the remaining 2 steps, etc.

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 the grid lines are far enough apart), but this can lead to the creation of rather large tree diagrams that could use the space more efficiently.

To detect unused space, you can simply scan the lines after the process described above and see if there are any intersecting grid lines and, possibly, rebuild some nodes to fill the gap.

Answer 3

Take a look at Dot . You can convert your tree to a point view and then use Graphviz to render in any format you like. For example, Doxygen uses it to represent the structure of a program.

Answer 4

Graphviz and mfgraph are powerful, but they are intended for general graphs and are probably too small for trees.

Try a Google search + layout + algorithm or look at the JavaScript Graphic Tree with the layout . The latter is old, but it uses HTML canvas and javascript, and it explains the code, so both the code and the approach should be portable.

Answer 5

Depending on the nature of your data, TreeMap may be more appropriate than a tinkertoy view.