<p>下面是一些代码,它们实现了别处描述的通用递归方法。树的内部表示是子节点的字符串(叶)或元组(对)。节点中间“片段”的内部表示是元组<code>(above, below, lines)</code>,其中<code>above</code>和{<cd3>}是根上下的行数,<code>lines</code>是每个部分行上的迭代器(左边没有空格)。在</p>
<pre><code>#!/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))
</code></pre>
<p>下面是一些输出示例:</p>
^{2}$
<p>还有一个更不对称的例子,也许可以说明为什么我在行尾之前不在左边填充空格(via<code>flatten</code>)。如果下半身被垫在左边,上臂的一些部分会穿过填充区域。在</p>
<pre><code> _/rrrrr
_/ \rrrrl
_/ \rrrl
_/ \_/rrlr
/ \ \rrll
/ \_/rlr
/ \rll
/ /lrrr
/ _/ _/lrrlrr
/ / \_/ \lrrlrl
/ / \lrrll
_/ _/ _/lrlrrr
\ / \ _/ \lrlrrl
\ / \_/ \lrlrl
\_/ \lrll
\ _/llrrr
\ _/ \llrrl
\_/ \llrl
\lll
</code></pre>
<p>这是一个“显而易见”的递归算法——魔鬼在细节中。没有“u”是最容易写的,这使得逻辑稍微复杂一些。在</p>
<p>也许唯一的“洞察力”是<code>gap_above = l_above</code>-也就是说右“臂”的长度与左子树右侧的长度相同(你需要读几遍)。它使事情相对平衡。请参阅上面的不对称示例。在</p>
<p>更详细地理解事情的一个好方法是修改<code>pad</code>例程,使其接受一个字符而不是{<cd8>},并为每个调用指定一个不同的字符。然后你就可以确切地看到哪个逻辑生成了哪个空间。这是使用A.B、C和D从上到下、从上到下调用pad时得到的结果(显然,当空间量为零时没有字符):</p>
<pre><code> _/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
</code></pre>
<p>这里有更多的解释<a href="http://www.acooke.org/cute/Printingbi0.html" rel="nofollow">here</a>(尽管这棵树略有不同)。在</p>