How can you print a binary tree on its side so the output looks like this?
__/a
__/ \b
\ _/c
\_/ \d
\e
(Prettier ascii-art welcome)
Here's some code that doesn't quite work:
def print_tree(tree):
def emit(node,prefix):
if "sequence" in node:
print "%s%s"%(prefix[:-1],node["name"])
else:
emit(node["left"],"%s_/ "%prefix.replace("/ "," /")[:-1].replace("_"," "))
emit(node["right"],"%s \\ "%prefix.replace("\\ "," \\")[:-1])
emit(tree,"")
Which outputs this:
_/hg19
_/ \rheMac2
_/ \mm9
/\_/bosTau4
/ \_/canFam2
_/ \pteVam1
\_/loxAfr3
\dasNov2
Scope creep: it would be excellent if you could pass in a function that will return the string to print of any node; in this way, I can sometimes print information about non-leave nodes too. So whether a node has anything to print is controlled by the function passed in as a parameter.
Here's some test-data in JSON:
{
"left": {
"left": {
"left": {
"left": {
"name": "hg19",
"sequence": 0
},
"right": {
"name": "rheMac2",
"sequence": 1
}
},
"right": {
"name": "mm9",
"sequence": 2
}
},
"right": {
"left": {
"name": "bosTau4",
"sequence": 3
},
"right": {
"left": {
"name": "canFam2",
"sequence": 4
},
"right": {
"name": "pteVam1",
"sequence": 5
}
}
}
},
"right": {
"left": {
"name": "loxAfr3",
"sequence": 6
},
"right": {
"name": "dasNov2",
"sequence": 7
}
}
}
Here's some code that implements the general, recursive approach described elsewhere. The internal representation of a tree is either a string (leaf) or a tuple (pair) of sub-nodes. The internal representation of the intermediate "fragment" of a node is the tuple (above, below, lines)
, where above
and below
are number of lines above and below the root, and lines
is an iterator over each partial line (without spaces to the left).
#!/usr/local/bin/python3.3
from itertools import chain
from random import randint
def leaf(t):
return isinstance(t, str)
def random(n):
def extend(t):
if leaf(t):
return (t+'l', t+'r')
else:
l, r = t
if randint(0, 1): return (l, extend(r))
else: return (extend(l), r)
t = ''
for _ in range(n-1): t = extend(t)
return t
def format(t):
def pad(prefix, spaces, previous):
return prefix + (' ' * spaces) + previous
def merge(l, r):
l_above, l_below, l_lines = l
r_above, r_below, r_lines = r
gap = r_below + l_above
gap_above = l_above
gap_below = gap - gap_above
def lines():
for (i, line) in enumerate(chain(r_lines, l_lines)):
if i < r_above:
yield ' ' + line
elif i - r_above < gap_above:
dash = '_' if i - r_above == gap_above - 1 else ' '
if i < r_above + r_below:
yield pad(dash + '/', 2 * (i - r_above), line)
else:
yield pad(dash + '/', 2 * gap_below - 1, line)
elif i - r_above - gap_above < gap_below:
if i < r_above + r_below:
yield pad(' \\', 2 * gap_above - 1, line)
else:
spaces = 2 * (r_above + gap_above + gap_below - i - 1)
yield pad(' \\', spaces, line)
else:
yield ' ' + line
return (r_above + gap_above, gap_below + l_below, lines())
def descend(left, t):
if leaf(t):
if left:
return (1, 0, [t])
else:
return (0, 1, [t])
else:
l, r = t
return merge(descend(True, l), descend(False, r))
def flatten(t):
above, below, lines = t
for (i, line) in enumerate(lines):
if i < above: yield (' ' * (above - i - 1)) + line
else: yield (' ' * (i - above)) + line
return '\n'.join(flatten(descend(True, t)))
if __name__ == '__main__':
for n in range(1,20,3):
tree = random(n)
print(format(tree))
Here's some example output:
_/rrrr
_/ \_/rrrlr
/ \ \rrrll
_/ \_/rrlr
/ \ \rrll
/ \ _/rlrr
/ \_/ \rlrl
_/ \_/rllr
\ \_/rlllr
\ \rllll
\ _/lrrr
\ _/ \lrrl
\ / \_/lrlr
\_/ \lrll
\ _/llrr
\_/ \llrl
\_/lllr
\_/llllr
\lllll
And a bit more asymmetric one that shows, perhaps, why I don't pad lines with spaces to the left until the end (via flatten
). If the lower half had been padded on the left some of the upper arm would cross the padded area.
_/rrrrr
_/ \rrrrl
_/ \rrrl
_/ \_/rrlr
/ \ \rrll
/ \_/rlr
/ \rll
/ /lrrr
/ _/ _/lrrlrr
/ / \_/ \lrrlrl
/ / \lrrll
_/ _/ _/lrlrrr
\ / \ _/ \lrlrrl
\ / \_/ \lrlrl
\_/ \lrll
\ _/llrrr
\ _/ \llrrl
\_/ \llrl
\lll
It's the "obvious" recursive algorithm - the devil is in the details. It was easiest to write without the "_", which makes the logic slightly more complex.
Perhaps the only "insight" is gap_above = l_above
- that's saying that the right "arm" has the length of the right side of the left subtree (you'll need to read that a few times). It makes things relatively balanced. See the asymmetric example above.
A good way of understanding things in more detail is to modify the pad
routine to take a character instead of ' '
and give a different character for each call. Then you can see exactly which logic generated which space. This is what you get using A. B, C and D for the calls to pad from top to bottom, above (obviously there's no character when the amount of space is zero):
_/rrrr
/ \rrrl
_/B _/rrlrr
/ \_/ \rrlrl
/AA \rrll
_/BBB _/rlrrr
/ \DD _/ \rlrrl
/AA \_/ \_/rlrlr
/AAAA \C \rlrll
/AAAAAA \_/rllr
_/AAAAAAAA \rlll
\DDDDDDDD _/lrrrr
\DDDDDD _/ \lrrrl
\DDDD / \lrrl
\DD _/B _/lrlrr
\_/ \_/ \lrlrl
\C \lrll
\_/llr
\lll
There's more explanation here (although the tree is very slightly different).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With