Tree構造の幅優先探索を実装してみます。
概要
幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。
幅優先探索 – Wikipedia
サンプルコード
treeを作成し、表示します。その後、幅優先探索をし、結果を出力します。以下では、結果の出力部分のみ紹介します。
from collections import deque
q = deque()
q.append(tree)
while len(q) > 0:
node = q.popleft()
if node is not None:
print(node.value)
q.append(node.left)
q.append(node.right)
実行結果（例）
0
\
1
____/ \___
2 5
____/ \___ / \
7 3 16 12
/ / \ /
11 4 9 15
\ __/ \__
14 13 6
/ \ \ /
17 18 19 8
/
10
0
1
2
5
7
3
16
12
11
4
9
15
14
13
6
17
18
19
8
