按广度优先顺序列出的字典图

Question

我有下图（在本例中是二叉树）作为字典。

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

我想要一个returns广度优先顺序列表表示的函数，如下所示：

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

如果我想要实现的目标不清楚，请告诉我，我会提供更多信息:)

到目前为止我的想法是从字典中读取根元素，然后获取子节点，然后读取每个子节点，同时将每个子节点推送到一个列表中，但这有点令人困惑，我会很感激一些帮助。

Answer 1

我认为您的预期输出不正确。有 6 个叶节点，每个节点有两个 None 个子节点，但您的预期输出中只有 4 个 None，而不是 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 属于节点 b、e、f 和 c。

按广度优先顺序列出的字典图

Dictionary graph to list by breadth-first order

python

binary-tree

binary-search

binary-search-tree

python-3.x