Вот код, который реализует общий, рекурсивный подход, описанный в другом месте. Внутреннее представление дерева - это либо строка (лист), либо кортеж (пара) узлов. Внутренним представлением промежуточного «фрагмента» узла является кортеж (above, below, lines), где above и below - это количество строк выше и ниже корня, а lines - итератор над каждой частичной линией (без пробелов слева).
#!/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))
Вот пример вывода:
_/rrrr
_/ \_/rrrlr
/\ \rrrll
_/ \_/rrlr
/\ \rrll
/ \ _/rlrr
/ \_/ \rlrl
_/ \_/rllr
\ \_/rlllr
\ \rllll
\ _/lrrr
\ _/ \lrrl
\ /\_/lrlr
\_/ \lrll
\ _/llrr
\_/ \llrl
\_/lllr
\_/llllr
\lllll
И немного более асимметричным один, который показывает, может быть, поэтому я никогда не набивать строки с пробелами слева до конца (через flatten). Если нижняя половина была заполнена слева, часть плеча пересекла бы мягкую область.
_/rrrrr
_/ \rrrrl
_/ \rrrl
_/ \_/rrlr
/\ \rrll
/ \_/rlr
/ \rll
/ /lrrr
/ _/ _/lrrlrr
/ /\_/ \lrrlrl
/ / \lrrll
_/ _/ _/lrlrrr
\ /\ _/ \lrlrrl
\ / \_/ \lrlrl
\_/ \lrll
\ _/llrrr
\ _/ \llrrl
\_/ \llrl
\lll
Это «очевидный» рекурсивный алгоритм - дьявол находится в деталях. Легче всего писать без «_», что делает логику несколько более сложной.
Возможно, единственным «прозрением» является gap_above = l_above - это говорит о том, что правая «рука» имеет длину правой части левого поддерева (вам нужно будет прочитать это несколько раз). Это делает вещи относительно сбалансированными. См. Асимметричный пример выше.
Хороший способ понять вещи более подробно - это изменить подпрограмму pad, чтобы взять символ вместо ' ' и дать различный символ для каждого вызова. Затем вы можете точно определить, какая логика сгенерировала это пространство. Это то, что вы получите с помощью A. B, C и D для звонков на площадку сверху вниз, сверху (очевидно, нет никакого символа, когда объем пространства равен нулю):
_/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
Там больше объяснений here (хотя дерево очень немного отличается).
Что вы пробовали? Я могу представить, что он включает в себя вычисление свойств дерева (глубина, ширина и т. Д.), Вычисление компоновки и создание искусства ASCII. –
@SimeonVisser добавил некорректный код – Will
Глядя на это, я задумался, что вы также должны отслеживать глубину дерева. У меня есть некоторый рудиментарный код на основе вашего сломанного кода, но он выглядит ужасно. Для каждой строки я пытаюсь выяснить, сколько дополнительного пространства у нее должно получиться, но восстановление для этой строки в настоящее время учитывает только самую низкую ветвь – Michael