Словарный график для перечисления по ширине в первом порядке - PullRequest
Новая
       32

Словарный график для перечисления по ширине в первом порядке

0 голосов
/ 17 сентября 2018

У меня есть следующий график (который в данном случае является двоичным деревом) в качестве словаря. 

G = {
    'root': ['4', '3'],
    '4': ['2', 'a'],
    '3': ['1', 'd'],
    '2': ['b', 'e'],
    '1': ['f', 'c']
    }

И я хочу функцию, которая возвращает представление списка в порядке по ширине, которое будет выглядеть следующим образом: 

arr = ['root','4','3','2','a','1','d','b','e',None,None,'f','c',None,None ]

Если то, чего я хочу достичь, неясно, пожалуйста, скажите мне, и я дам больше информации:)

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

1 Ответ

0 голосов
/ 17 сентября 2018

Я не думаю, что ваш ожидаемый результат правильный.Существует 6 конечных узлов, каждый с двумя None дочерними узлами, и все же у вас есть только 4 None s в ожидаемом выводе, а не 12.

со следующим кодом: 

from collections import deque
def bf(tree, node='root'):
    output = []
    queue = deque([node])
    while queue:
        node = queue.popleft()
        output.append(node)
        if node is not None:
            for i in tree.get(node, [None, None]):
                queue.append(i)
    return output
print(bf(G))

Будет выведено: 

['root', '4', '3', '2', 'a', '1', 'd', 'b', 'e', None, None, 'f', 'c', None, None, None, None, None, None, None, None, None, None]

Обратите внимание на дополнительные 8 None s, которые принадлежат узлам b, e, f и c.

...