IT資格用語解説基本情報技術者試験・データ構造の種類
木の探索方法と走査順
更新日:
用語解説
木の探索・走査は、木の節点を深さ方向又は幅方向に訪れ、二分木では根を訪れる位置により先行順・中間順・後行順へ分類する方法です。
■ 試験で押さえるポイント
深さ優先探索（DFS）は一つの枝を深く進んでから戻り、再帰又は明示的なスタックで実装します。
幅優先探索（BFS）は根に近い層から順に訪れ、キューで実装し、辺重みが同じ木・グラフの最短辺数を求められます。
先行順は根→左→右で木の複製・前置式、 中間順は左→根→右で二分探索木の昇順走査に使います。
後行順は左→右→根で、子の処理後に親を処理する削除、サイズ計算、後置式等に向きます。
■ 選択肢での判断ポイント
先行は根が先、中間は根が中央、後行は根が後です。DFSはスタック、BFSはキューを対応付けます。
例: 根A、左B、右Cなら、先行順はA-B-C、中間順はB-A-C、後行順はB-C-Aです。