C How to "draw" a Binary Tree to the console

Answer 1

This is difiicult. What do you do when, from your example, the "8" node has a left child? This issue explains why trees are in practice almost always displayed vertically, as in various file managers.

Answer 2

I think you shouldn't code that yourself, but have a look at Tree::Visualize which seems to be a nice Perl implementation with different possible styles and use/port one of the algorithms there.

Answer 3

Some hints: the spacing between nodes at the same depth, (e.g., 2 and 4 or 3 and 8 in your example), is a function of the depth.

Each printed row consists of all nodes with the same depth, printed from the leftmost node to the rightmost node.

So you need a way to, for example, arrange your nodes in arrays of rows, according to their depth, in order of their left-most-ness.

Starting from the root node, a breadth-first search will visit nodes in the order of depth and left-most-ness.

Spacing between nodes can be found by finding the maximum height of the tree, using some constant width for the deepest nodes, and doubling that width for every lesser depth, so that the width for any depth = ( 1 + maxdepth - currentdepth ) * deepestwidth.

That number gives you the printed "horizontal width" of each node at any particular depth.

A left node is horizontally positioned in the left half of its parent's width, a righ node in the right half. You'll insert dummy spacers for any node that doesn't have parents; an easier way to do this would be to ensure that all leaves are at the same depth as the deepest node, with blank as their value. Obviously, you'll also have to compensate for the width of the values, perhaps by making the greatest depth's width at least as wide as the printed (decimal representaion, presumably) of he largest valued node.

Answer 4

Check out Printing Binary Trees in Ascii

Answer 5

Look at the output of pstree command in Linux. It does not produce the output in the exact form that you want, but IMHO it's more readable that way.

Answer 6

I second litb's recommendation. I had to do this lately to print the VAD tree of a Windows process and I used DOT language (just print out nodes from your binary tree walking function):

http://en.wikipedia.org/wiki/DOT_language

For example, your DOT file would contains:

digraph graphname {
     5 -> 3;
     5 -> 8;
     3 -> 4;
     3 -> 2;
}

You generate the graph with dotty.exe or convert it to PNG using dot.exe.