#Pythonで学ぶアルゴリズム< 木構造 >
##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第11弾として木構造を扱う．
##木構造
#####幅優先探索
・階層ごとに見ていくような感じ
・何か1つだけ合致するものを見つける場合に高速に処理できる
・探索途中のノードをすべて保持 ⇒ メモリを大きく消費してしまう
#####深さ優先探索
・限界まで進んで，また戻ってくる方法（バックトラックともいう）
・すべての（ある程度の深さまでの）答えを見つけるときによく使われる
・再帰処理を使うことが多い
・3種の異なるルートがある（行きがけ・帰りがけ・通りがけ）
##木構造の処理ルート
####幅優先探索
おおまかなイメージ図を次に示す．
実際に処理順を各ノードに記したものを次に示す．
幅優先ははじめに書いたとおり，階層ごとに処理している．
####深さ優先探索
おおまかなイメージ図を次に示す．
3種のルートすべては上記のおおまかなイメージに従うが，ノードを処理するタイミングによりそれらは分類される．
#####①行きがけ順
各ノードの子をたどる前にそのノードを処理
#####②帰りがけ順
各ノードの子をすべてたどった後でそのノードを処理
#####③通りがけ順
2分木の左側の子ノードをたどった後に処理し，右側の子のノードをたどる．
##実装
pythonに実装するが，ここでは簡易のため，リストで木構造を表現することとする．その対応付けは次の通りである．
以下では，幅優先探索，深さ優先探索について簡単な実装サンプルコードとそのときの出力を示す．
#####コード（幅優先探索）
"""
2020/12/29
@Yuya Shimizu
幅優先探索
"""
tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
[13,14], [], [], [], [], [], [], [], []]
data = [0]
while len(data) > 0:
pos = data.pop(0) #pop: dataから0を取り出す（dataからは0が要素が消える）
print(pos, end = ' ')
for i in tree[pos]:
data.append(i)
#####出力
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
上記の図と照らし合わせると，幅優先探索の順で処理されていることが分かる．
#####コード（深さ優先探索：行きがけ順）
"""
2020/12/29
@Yuya Shimizu
深さ優先探索１：行きがけ順
"""
tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
[13,14], [], [], [], [], [], [], [], []]
def search(pos):
print(pos, end = ' ') #配下のノードを調べる前に出力
for i in tree[pos]: #配下のノードを調べる
search(i) #再帰的に探索
search(0)
#####出力
0 1 3 7 8 4 9 10 2 5 11 12 6 13 14
上記の図と照らし合わせると，深さ優先探索行きがけ順で処理されていることが分かる．
#####コード（深さ優先探索：帰りがけ順）
"""
2020/12/29
@Yuya Shimizu
深さ優先探索２：帰りがけ順
"""
tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
[13,14], [], [], [], [], [], [], [], []]
def search(pos):
for i in tree[pos]: #配下のノードを調べる
search(i) #再帰的に探索
print(pos, end = ' ') #配下のノードを調べた後に出力
search(0)
#####出力
7 8 3 9 10 4 1 11 12 5 13 14 6 2 0
上記の図と照らし合わせると，深さ優先探索帰りがけ順で処理されていることが分かる．
#####コード（深さ優先探索：通りがけ順）
"""
2020/12/29
@Yuya Shimizu
深さ優先探索３：通りがけ順
"""
tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
[13,14], [], [], [], [], [], [], [], []]
def search(pos):
if len(tree[pos]) == 2: #子が２つあるとき
search(tree[pos][0])
print(pos, end = ' ') #左のノードと右のノードの間に出力
search(tree[pos][1])
elif len(tree[pos]) == 1: #子が１つのとき
search(tree[pos][0])
print(pos, end = ' ') #左のノードを調べた後に出力
else: #配下のノードがないとき
print(pos, end = ' ')
search(0)
#####出力
7 3 8 1 9 4 10 0 11 5 12 2 13 6 14
上記の図と照らし合わせると，深さ優先探索通りがけ順で処理されていることが分かる．
##感想
今回，コードの中でpop()の使い方を知れたことはよかった．また，木構造について，特に深さ優先探索の中にもタイミングにより３つの異なる探索ルートがあることを知れた．ここでは，サンプルプログラムを動かしアルゴリズムの動作のみ確認したが，ロボットの意志決定のときにも使われることもあると学んだため，今後それも実装できたらと思う．
##参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社