木の探索方法と走査順
更新日:
用語解説
木の探索・走査は、木の全ての節点を決まった順に訪れることです。深さ方向に進む深さ優先探索と、浅い層から順に進む幅優先探索があります。
■ 試験で押さえるポイント
深さ優先探索は一つの枝を奥まで進んでから戻る方法で、スタック（または再帰）で実装します。
幅優先探索は根に近い層から順に訪れる方法で、キューで実装します。
二分木の深さ優先の走査は、根を訪れる順番で先行順（根→左→右）、中間順（左→根→右）、後行順（左→右→根）に分かれます。
■ 選択肢での判断ポイント
根が先なら先行順、真ん中なら中間順、最後なら後行順です。二分探索木を中間順でたどると昇順になります。
例: 根A、左の子B、右の子Cの木なら、先行順はA→B→C、中間順はB→A→C、後行順はB→C→Aです。