Tree構造の幅優先探索を実装してみます。
概要
深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。
深さ優先探索 – Wikipedia
サンプルコード
treeを作成し、表示します。その後、深さ優先探索をし、結果を出力します。以下では、結果の出力部分のみ紹介します。
def rec(node):
if node is not None:
print(node.value)
rec(node.left)
rec(node.right)
rec(tree)実行結果（例）
0
\
1
____/ \___
2 5
____/ \___ / \
7 3 16 12
/ / \ /
11 4 9 15
\ __/ \__
14 13 6
/ \ \ /
17 18 19 8
/
10
0
1
2
7
11
14
17
18
3
4
13
19
6
8
10
9
5
16
12
15
