树的广度优先遍历，Python

Question

我研究了树的深度优先遍历。

def _dfs(tree, res):
    if tree:
        res += [tree.key]
        _dfs(tree.left, res)
        _dfs(tree.right, res)
    return res

我似乎找不到广度优先搜索的解决方案。是否需要使用队列或栈？

谢谢！

- user908015

Answer 1

您可以选择使用双端队列（deques）来实现。这是Magnus Lie Hetland的BFS算法的一个经典实现，使用了FIFO队列。

from collections import deque

def bfs(G, s):
    P, Q = {s: None}, deque([s]) 
    while Q:
        u = Q.popleft() 
        for v in G[u]:
            if v in P: continue 
            P[v] = u 
            Q.append(v)
    return P

- luke14free

Answer 2

是的，你需要使用一个队列来存储已经检查但尚未递归到的节点。

从队列中的根节点开始，然后重复 [弹出一节点，并对其每个子节点执行您需要的操作（res += [tree.key]），并将其推入队列。]

- Andrew Aylett

---

当我将它们存储在堆栈中时，我是按深度优先遍历来存储它们吗？ - user908015

抱歉，队列不是栈。我已经修复/扩展了我的答案。 - Andrew Aylett