Pythonで学ぶアルゴリズム　第11弾：木構造

# #Pythonで学ぶアルゴリズム< 木構造 >

##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第11弾として木構造を扱う．

##木構造
#####幅優先探索
・階層ごとに見ていくような感じ
・何か1つだけ合致するものを見つける場合に**高速に処理**できる
・探索途中のノードをすべて保持　⇒　メモリを大きく消費してしまう
#####深さ優先探索
・限界まで進んで，また戻ってくる方法（**バックトラック**ともいう）
・すべての（ある程度の深さまでの）答えを見つけるときによく使われる
・再帰処理を使うことが多い
・3種の異なるルートがある（行きがけ・帰りがけ・通りがけ）

##木構造の処理ルート
####幅優先探索
おおまかなイメージ図を次に示す．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/9eea02bf-c186-1f72-3dd9-27e3d92afa22.png)
実際に処理順を各ノードに記したものを次に示す．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/9a3169e5-ec0d-72f3-1a19-02cf2a859823.png)
幅優先ははじめに書いたとおり，階層ごとに処理している．

####深さ優先探索
おおまかなイメージ図を次に示す．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/618e2f8d-2447-018e-57e8-4f6be8329e13.png)
3種のルートすべては上記のおおまかなイメージに従うが，ノードを処理するタイミングによりそれらは分類される．
#####①行きがけ順
各ノードの子をたどる前にそのノードを処理
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/d8dae03c-a7b8-c076-c785-6341dadb8472.png)

#####②帰りがけ順
各ノードの子をすべてたどった後でそのノードを処理
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/1f52026c-2520-0f22-1481-5131a16418ae.png)


#####③通りがけ順
2分木の左側の子ノードをたどった後に処理し，右側の子のノードをたどる．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/74669ec7-a4d3-cfbd-59d6-8254488f4818.png)

##実装
pythonに実装するが，ここでは簡易のため，リストで木構造を表現することとする．その対応付けは次の通りである．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/951300/f9ff37d4-ced3-0659-c530-10045bfe3483.png)

以下では，幅優先探索，深さ優先探索について簡単な実装サンプルコードとそのときの出力を示す．

#####コード（幅優先探索）
```python:breadth_search.py
"""
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
```
上記の図と照らし合わせると，幅優先探索の順で処理されていることが分かる．


#####コード（深さ優先探索：行きがけ順）
```python:depth_search1.py
"""
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 
```
上記の図と照らし合わせると，深さ優先探索行きがけ順で処理されていることが分かる．


#####コード（深さ優先探索：帰りがけ順）
```python:depth_search2.py
"""
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  
```
上記の図と照らし合わせると，深さ優先探索帰りがけ順で処理されていることが分かる．


#####コード（深さ優先探索：通りがけ順）
```python:depth_search3.py
"""
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で始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　 増井 敏克　著　　翔泳社