「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#25 - Qiita

順序木と無順序木 兄弟関係にあるノードの順序関係を区別する木が順序木、区別しない木が無順序木 順序木の探索 順序木の探索は大きく分けて2つ 幅優先探索/横型探索・・・レベルの低い点から始めて左側から右側へとなぞり、それが終わると次のレベルにくだる方法 深さ優先探索/縦型探索・・・葉に到達するまで下流に下るのを優先する方法。葉に到達した場合はいったん親に戻って、それから次のノードへたどっていきます。縦型探索は次の3種類の走査法に分類されます。(A(親)B(子)C(子)というノードを例に補足) ・行きがけ順(前順/先行順)・・・ノードに立ち寄る→左の子にくだる→右の子にくだる（まず最初にAに立ち寄る） ・通りがけ順(間順/中間順)・・・左の子にくだる→ノードに立ち寄る→右の子にくだる（BからCに行く途中でAに立ち寄る） ・帰りがけ順(後順/後行順)・・・左の子にくだる→右の子にくだる→ノードに