Распечатайте содержимое дерева так, чтобы каждый родитель покрывал всех своих потомков - PullRequest
Новая
       34

Распечатайте содержимое дерева так, чтобы каждый родитель покрывал всех своих потомков

0 голосов
/ 29 июня 2019

Часть проблемы требует, чтобы каждый родитель охватывал всех своих детей.Если родительская строка слишком короткая, подчеркивания добавляются.Любое оставшееся пространство имеет добавленные периоды.

* Примечание: входные деревья могут иметь любое количество дочерних элементов *

Пока у меня есть функция (add_brackets), которая добавляет скобки вкаждая строка в соответствии со спецификациями для задачи.Именно в этих скобках подчеркивания добавляются при необходимости.

Вторая функция (подчеркивания) вычисляет, сколько требуется подчеркивания.

Последняя функция рекурсивно распечатывает дерево в порядке уровней.

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

def add_brackets(x):
  row = ''
  for i in x:
    row = row+'['+i+']'
  return row

def underscores(node):
  parent, children = node
  num = 0
  for child in children:
    num += len(child)+2
  num -= 2
  if len(parent) > canlen:
    return 
  return '_'*num

def level_order(*nodes):
    if not nodes:
      return 
    labels,childrens = zip(*nodes)
    print(add_brackets(labels))
    flattened_children = [c for children in childrens for c children]  
    level_order(*flattened_children)

tree = eval(input('Enter tree: '))
print(level_order(tree))

Следующее дерево, 

tree = ("hello", (("a", ()), ("b", (("cde", ()), ("fg", ())))))

Должно иметь вывод, 

[hello_____]
[a][b______]
...[cde][fg]

и, 

tree = ("supercalifragilisticexpialidocious",(("a",(("b",(("candy",()),)),("onomatopoeia",()),)),("d",(("egg",(("f",()),)),)),))

Должно быть, 

[supercalifragilisticexpialidocious]
[a__________________][d__]..........
[b____][onomatopoeia][egg]..........
[candy]..............[f]............

Как добавить правильное количество подчеркиваний и периодов?

1 Ответ

0 голосов
/ 30 июня 2019

Я решил проблему, которую вы описываете, и это было больше работы, чем я ожидал (хотя и меньше 1500 байт кода). Основная модель - работать снизу вверх, чтобы получить подчеркивания, а затем снизу вниз, чтобы получить отступы. Вот схема функций, которые я определил для ее решения: 

def height_tree(node):

Рекурсивно, сначала глубина. Простой код для расчета высоты дерева. Это необходимо только следующей функции, чтобы различать узел типа [a], у которого нет дочерних элементов, но для которого требуется подделка, и для узла, у которого нет дочерних элементов, для которого мы не хотим добавлять поддельные. . 

def covered_tree(node, level=0):

Рекурсивно, сначала глубина. Сначала выполняется рекурсивная обработка, затем определяется ширина покрытия. Если значение level по умолчанию равно нулю, установите его на height_tree() выше. Возвращает действительное дерево: 

('[hello_____]', (('[a]', (('...', ()),)), ('[b______]', (('[cde]', ()), ('[fg]', ())))))

но родительские строки были расширены с помощью скобок и подчеркиваний. Дает узлы, такие как [a] и [onomatopoeia] с поддельными дочерними элементами, состоящие из заполнения периода 

def padded_tree(node, tail=True):

Рекурсивно, сначала глубина. Сначала работает дополнение, а затем повторяется. Обрабатывает только заполнение в самом правом конце ветви, внутреннее заполнение было обработано covered_tree() выше. Возвращает действительное дерево: 

('[supercalifragilisticexpialidocious]', (('[a__________________]', (('[b____]', (('[candy]', ()),)), ('[onomatopoeia]', (('..............', ()),)))), ('[d__]..........', (('[egg]..........', (('[f]............', ()),)),))))

но родительские строки были расширены с добавлением точки. 

def print_tree(node, line_width=0):

Итеративный, сначала ширина. Печатает дерево, устанавливая line_width на ширину верхнего узла, так как оно охватывает все. Считает ширину печати до нуля, выводит новую строку и сбрасывает ширину печати обратно до line_width.

OUTPUT 

>>> tree = ("hello", (("a", ()), ("b", (("cde", ()), ("fg", ())))))
>>> print_tree(padded_tree(covered_tree(tree)))
[hello_____]
[a][b______]
...[cde][fg]
>>> 
>>> tree = ("supercalifragilisticexpialidocious",(("a",(("b",(("candy",()),)),("onomatopoeia",()),)),("d",(("egg",(("f",()),)),)),))
>>> print_tree(padded_tree(covered_tree(tree)))
[supercalifragilisticexpialidocious]
[a__________________][d__]..........
[b____][onomatopoeia][egg]..........
[candy]..............[f]............
>>>

Я не совсем понимаю, как работает функция cover_tree. Ты можешь уточни пожалуйста?

Поскольку это критическая функция, давайте разберем ее: 

def covered_tree(node, level=0):

Если level равен нулю, по умолчанию установите level на результат height_tree(node). Разделите узел на две части: родитель (метка) и список дочерних элементов (узлы).

Выполните нашу рекурсию, создав новый список дочерних элементов (узлов), который является результатом вызова covered_tree() для каждого дочернего элемента, но с явной передачей level - 1. Для каждого из этих новых дочерних элементов суммируйте len() (ширину) их меток. Из этого подсчета вычтите len() (ширину) родительской метки и ширину 2, чтобы учесть скобки.

Теперь мы готовы создать наш возвратный узел. Это кортеж, который состоит из: нашего родителя, отформатированного в скобках плюс количество подчеркиваний, которые мы только что вычислили на предыдущем шаге; наш новый список детей. Однако, если имеется нет потомков, и level больше единицы, то вместо пустых потомков мы возвращаем поддельный список потомков, состоящий из потомков с меткой строка периодов, чьи собственные дочерние элементы являются пустым кортежем (т. е. нашим пустым списком дочерних элементов). Длина этой строки периодов снова равна len() (ширина) нашей родительской метки плюс 2 для учета скобок: 

('[hello_____]', (('[a]', (('...', ()),)), ('[b______]', (('[cde]', ()), ('[fg]', ())))))
...