Tree visualization algorithm

问题:

Is there some algorithm for tree data structure visualization? I tried googling, but couldnt find any. I'm pretty sure there has to be some algorithm for this not that simple task. Or anyone has some ideas?

回答1:

Assumption: you want each node to be displayed such that it is centered above its child nodes.

To achieve this, calculate the width of each node, which I define as the amount of horizontal space required to display this node's entire subtree, such that it doesn't overlap with its left or right siblings' subtrees.

This leads to:

width = 1 + sum(widths of children's nodes)

So, do a depth-first traversal through the tree to calculate each node's width. To display, do a breadth-first traversal to draw the tree level by level.

This is the rough idea of how to go about it. You might want to tweak the width calculation depending on the details of how you would like to render the tree.

回答2:

Tree-mapping is probably what you are looking for. Graphviz is good for visualizing graph structures not specialized for tree structures. I could not find it again but I remember have read in a scientific article that treemaps (I think the voronoi) are optimal to represent tree structures, regarding the place they consume and the area can be used to represent some unit (like byte size for example).

Here are some alternatives.

Here is a good list of articles and other information about the topic.

回答3:

You can use the DOT language with graphviz for example.

回答4:

You can also print the tree left-to-right i.e. root at the very left, the first level right to that and so on. You'll find the tree printed with each level on it's own 'column'. The algorithm is somewhat like this:

print(node, spaces):
    if node has left child:
        print(left_child, spaces + '    ')
    print spaces + node + '\n'
    if node has right child:
        print(right_child, spaces + '    ')

This algorithm will print one tree node per line. Each level of the tree will be indented to the right by some spaces. This algorithm will print the items in ascending order, but the descending order may be achieved by processing the right child first.