Oto niektóre kodu, który implementuje generał rekurencyjnej metody opisanej w innym miejscu. Wewnętrzna reprezentacja drzewa to ciąg (liść) lub krotka (para) podnagłówków. Wewnętrzna reprezentacja pośredniego "fragmentu" węzła jest krotką (above, below, lines), gdzie above i below są liczbą linii powyżej i poniżej podstawy, a lines jest iteratorem nad każdą linią częściową (bez spacji po lewej stronie).
#!/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))
Oto kilka przykładów wyjścia:
_/rrrr
_/ \_/rrrlr
/\ \rrrll
_/ \_/rrlr
/\ \rrll
/ \ _/rlrr
/ \_/ \rlrl
_/ \_/rllr
\ \_/rlllr
\ \rllll
\ _/lrrr
\ _/ \lrrl
\ /\_/lrlr
\_/ \lrll
\ _/llrr
\_/ \llrl
\_/lllr
\_/llllr
\lllll
I nieco bardziej asymetryczne, który pokazuje, być może, dlaczego ja nie linie pad z pomieszczeń w lewo, aż do końca (przez flatten). Gdyby dolna część była wyściełana po lewej stronie, część górnego ramienia przechodziła przez wyściełany obszar.
_/rrrrr
_/ \rrrrl
_/ \rrrl
_/ \_/rrlr
/\ \rrll
/ \_/rlr
/ \rll
/ /lrrr
/ _/ _/lrrlrr
/ /\_/ \lrrlrl
/ / \lrrll
_/ _/ _/lrlrrr
\ /\ _/ \lrlrrl
\ / \_/ \lrlrl
\_/ \lrll
\ _/llrrr
\ _/ \llrrl
\_/ \llrl
\lll
To "oczywisty" algorytm rekurencyjny - diabeł tkwi w szczegółach. Najłatwiej było pisać bez "_", co czyni logikę nieco bardziej złożoną.
Być może jedynym "wglądem" jest gap_above = l_above - to znaczy, że prawe "ramię" ma długość prawej strony lewego poddrzewa (musisz to przeczytać kilka razy). To sprawia, że rzeczy są względnie zrównoważone. Zobacz powyższy asymetryczny przykład.
Dobrym sposobem na bardziej szczegółowe zrozumienie jest zmodyfikowanie rutyny pad w celu zabrania postaci zamiast ' ' i nadania innej postaci każdemu połączeniu. Wtedy widać dokładnie, która logika wygenerowała jaką przestrzeń. To jest to, co można dostać za pomocą A. B, C i D dla połączeń pad od góry do dołu, od góry (oczywiście nie ma znaków, gdy ilość miejsca jest 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
Jest więcej wyjaśnienie here (chociaż drzewo jest bardzo nieznacznie różne).
Co próbowaliście? Mogę sobie wyobrazić, że wymaga to obliczenia właściwości drzewa (głębokość, szerokość itd.), Obliczeń układu i wygenerowania sztuki ASCII. –
@SimeonVisser dodał trochę złamanego kodu – Will
Patrząc na to, myślę, że powinieneś również śledzić głębokość drzewa. Mam pewien podstawowy kod na podstawie twojego zepsutego kodu, ale wygląda okropnie. Dla każdego wiersza próbuję dowiedzieć się, ile dodatkowego miejsca powinien on mieć, ale rekonstrukcja dla tego wiersza odpowiada obecnie za najniższy numer oddziału – Michael