応用情報技術者平成29年秋期 午前5
配列A[1]，A[2]，…，A[n]でA[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i＋1]とみなすことによって，2分木を表現する。このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。
１、幅優先探索
根から近い順に調べていくこと
２、深さ優先探索
根からできるだけ分岐せずにいちばん深い葉の部分にまで到達してから、ひとつ前の節まで戻り他方の探索を行う方法
３種類があります：
・行きがけ順(先行順) ※根から
根 → 左の部分木 → 右の部分木 順
・通りがけ順(中間順) ※葉から
左の部分木 → 根 → 右の部分木 順
・帰りがけ順(後行順) ※葉から
左の部分木 → 右の部分木 → 根 順
参照：