Вывести содержимое дерева в порядке уровней, используя функцию eval для чтения входного дерева в python - PullRequest
Новая
       21

Вывести содержимое дерева в порядке уровней, используя функцию eval для чтения входного дерева в python

1 голос
/ 29 июня 2019

Часть проблемы требует, чтобы дерево печаталось в порядке уровней, поэтому, если дерево ввода: 

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

тогда вывод должен быть, 

hello

a b

cde fg

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

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

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

Большинство подобных проблем имеют тенденцию использовать класс Node и / или компонент очереди, которые я не нашел полезными для этой проблемы, и я не могу найти случаев, когда функция eval используется для ввода.

Это то, что я имею до сих пор, 

def level_order(node):
  label, children = node
  print(label)
  for child in children:
    level_order(child)

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

Моя текущая программа способна распечатать содержимое, что, по моему мнению, является обходом предварительного заказа. Как заставить его печатать в порядке уровней?

1 Ответ

1 голос
/ 29 июня 2019

вам нужно пройти первую ширину дерева 

def level_order(*nodes):
    if not nodes: # base case
       return
    # all the labels and all the groups of chilren for this "level"
    labels,childrens = zip(*nodes)
    print("\t".join(labels))
    # flatten the list so instead of [[c1,c2],[c3,c4,c5,...]] we get [c1,c2,c3,...]
    flattened_children = [c for children in childrens for c in children]
    # call recursively
    level_order(*flattened_children)

level_order(("hello", (("a", ()), ("b", (("cde", ()), ("fg", ()))))) )
...