木構造での探索行きがけ順について

行きがけ順の勉強をpythonでやっているのですが、tree[pos]の意味がわからず困っています。
そもそも、posは何を表しているんでしょうか？
また、最後のsearch (0)もよくわかりません…。
よろしくお願いいたします。

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)

toast-uz

2020/11/03 12:16

このtreeが、どういう形の木構造を定義しているか、わかりますでしょうか？そもそも、それがわからないと、コードは読めないと思います。

lime_penguins

2020/11/03 12:28

自信が無いのですが、0番の要素にぶら下がっているのが1,2番。1番の要素にぶら下がっているのは3,4番、というように、繋がっている構造だと思っていました。

toast-uz

2020/11/03 13:02

そうです！それがわかれば、質問されたことの理解も容易です。 search(pos)は、pos番目の要素の探索（search(0)は、まず0番（根元）から探索開始、という意味） tree[pos]はpos番目の分岐の中身（tree[0] なら [1, 2]、tree[1] なら [3, 4]）を理解すれば、動作が順に追えると思います。

行動規範の内容に同意します

回答1件

ベストアンサー

ざっと見ると、このtreeリストの角要素がそれぞれノードを表わしていて、ノードはノードは子ノードを2つ持っていてそれがリストで表わされています。

ざっと絵にするとこんな感じです。

ノード0の子は1と2で、1の子は3と4で..というような感じです。

esarch関数は、引数がノード番号でそのノードの下のノードを深さ優先で全て訪れるようになっています。ノード7以降は空=葉ノードなのでそこで探索は止まります。
再帰関数なので、慣れないと追い掛けるのはむずかしいかもしれませんが、以下のように呼び出されます。インデントがループ階層のつもりです。

text
1search(0)
2  -> search(1) 
3     -> search(3) 
4       -> search(7) ★これがループしない 
5       -> search(8) ★これもループしない
6     -> search(4)
7       -> search(9) ★これがループしない
8       -> search(10) ★これもループしない