Печатать двоичное дерево на своей стороне

Ответ 1

Здесь приведен код, который реализует общий, рекурсивный подход, описанный в другом месте. Внутреннее представление дерева - это либо строка (лист), либо кортеж (пара) узлов. Внутреннее представление промежуточного "фрагмента" node представляет собой набор (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

Здесь больше объяснений здесь (хотя дерево очень немного отличается).

Ответ 2

Сделать структуру представления, включающую строковый массив и номер строки "лепестка".

rep (лист) - [0, repr (значение листа)]

rep (nonleaf), заданный top = nonleaf.left и bottom = nonleaf.right:

Поместите каждую строку rep (сверху) с пробелами, если над верхним лепестком, или с косой чертой в соответствующей позиции, если ниже. Аналогичным образом проложите каждую строку rep (внизу) пробелами, если ниже нижнего лепестка, или с обратной косой чертой в соответствующем положении, если указано выше. repr (nonleaf) - это [высота вершины, заполненные строки сверху, а затем заполненные строки внизу).

Пример:

rep(a): [0, ["a"]]
rep(b): [0, ["b"]]
rep(ab): [1, ["/"+"a", "\"+"b"]]
rep(c): [0, ["c"]]
rep(d): [0, ["d"]]
rep(cd): [1, ["/"+"c", "\"+"d"]]
rep(e): [0, ["e"]]
rep(cde): [2, [" "+"/c", "/" + "\d", "\" + "e"]]
rep(abcde): [2, [" "+"/a", "/"+"\b", "\ "+" /c", " \" + "/\d", "  " + "\e"]]

Обратите внимание, что в верхнем случае ширина прокладки - это количество линий ниже лепестка; в нижнем случае ширина прокладки соответствует лепестку. Таким образом, в случае (abcde) вершина имеет 2 строки и лепесток 1, поэтому заполнение равно (2 - 1 == 1) одного символа; у основания есть лепесток 2, поэтому заполнение - 2 символа.

Если вы хотите, вы также можете добавить "_" на каждом нелибе в строке (petal-1) th (и дополнительное пространство для всех других строк).

Очевидно, что ни один из них не является кодом ( "\" - это синтаксическая ошибка, ожидающая появления), но отсюда не должно быть слишком сложно реализовать.

Ответ 3

Вам нужно подходить к этому рекурсивно и отслеживать размеры отдельных поддеревьев. В частности, где корень. Не сбалансированное дерево может выглядеть так:

/
\/
 \/
  \/
   \

Теперь подумайте, что вы уже создали это дерево, что вам нужно, чтобы преобразовать это в следующее при добавлении родительского уровня.

  /
 /\/
/  \/
\   \/
 \   \
  \

Основная идея - начать с листьев. Они тривиальны. Затем определите способ агрегирования двух поддеревьев, учитывая, что они имеют различное количество строк и другую позицию корня поддерева node.

Ответ 4

Вот красивое боковое дерево, которое просто помогло мне в отладке проекта: http://www.acooke.org/cute/ASCIIDispl0.html

Результаты напоминают макет каталога плагина VIM NERDtree, если вы это видели.

Вот моя повторная реализация как метод __str__ в двоичном дереве:

def __str__(self):
    """Recursive __str__ method of an isomorphic node."""
    # Keep a list of lines
    lines = list()
    lines.append(self.name)
    # Get left and right sub-trees
    l = str(self.left).split('\n')
    r = str(self.right).split('\n')
    # Append first left, then right trees
    for branch in l, r:
        # Suppress Pipe on right branch
        alt = '| ' if branch is l else '  '
        for line in branch:
            # Special prefix for first line (child)
            prefix = '+-' if line is branch[0] else alt
            lines.append(prefix + line)
    # Collapse lines
    return '\n'.join(lines)