python - ツリーの幅優先トラバーサル、Python

Question

ツリーの深さ優先トラバーサルを見つけました。

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

幅優先探索の解決策が見つからないようです。キューまたはスタックを使用する必要がありますか?

ありがとう！！

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

Answer 2

はい、チェックしたがまだ再帰していないノードを保持するためにキューを使用する必要があります。

キュー内のルート ノードから始めて、[ノードをポップし、その子のそれぞれについて、必要なアクションを実行し ( res += [tree.key])、それをキューにプッシュする] を繰り返します。