木の巡回（走査）とは？
木の巡回（走査）とは、木構造やグラフのすべての節点をある規則に沿って訪問する方法。深さ優先探索（DFS）は行けるところまで深くたどってから戻る方式、幅優先探索（BFS）は根に近い節点から順に階層ごとに訪問する方式。二分木の巡回には「行きがけ順（前順）」「通りがけ順（中順）」「帰りがけ順（後順）」がある。
応用情報技術者試験の過去問では2回出題されています（2017年度〜2021年度）。
きのじゅんかい
木の巡回（走査）の意味
木構造やグラフのすべての節点をある規則に沿って訪問する方法。深さ優先探索（DFS）は行けるところまで深くたどってから戻る方式、幅優先探索（BFS）は根に近い節点から順に階層ごとに訪問する方式。二分木の巡回には「行きがけ順（前順）」「通りがけ順（中順）」「帰りがけ順（後順）」がある。
木の巡回（走査）の具体例
迷路の最短経路を求めるには、階層順に探索して最初に到達した経路が最短になる幅優先探索が適する。ファイルシステムを再帰的に全探索する処理は深さ優先探索の考え方に近い。
木の巡回（走査）は試験でどう引っ掛けられる？
木の巡回（走査）と関連する用語
木の巡回（走査）が出た過去問
配列A[1]、A[2]、…、A[n]で、A[1]を根とし、A[i]の左側の子をA[2i]、右側の子をA[2i+1]とみなすことによって、2分木を表現する。このと…
正解：幅優先探索
要点：配列表現の並び順は2分木の幅優先探索と一致する
この配列表現ではA[1]が根、A[2]とA[3]が深さ1、A[4]〜A[7]が深さ2というように、同じ深さのノードが配列上で連続して並ぶ。したがって配列を先頭から順に調べることは、根に近い階層から順に、各階層内は左から右へ辿ることを意味し、幅優先探索に相当する。
出典：平成29年度 秋期 応用情報技術者試験 午前 問5（IPA）配列A[1]，A[2]，…，A[n]で、A[1]を根とし、A[i]の左側の子をA[2i]、右側の子をA[2i+1]とみなすことによって、2分木を表現する。このと…
正解：幅優先探索
要点：ヒープ形式の配列表現の添字順は幅優先の訪問順
この配列表現では、添字の小さい順に根、深さ1の全ノード、深さ2の全ノード…と並ぶ。したがって配列を先頭から順に走査することは、根から始めて同じ深さのノードを左から右へ順に訪問することに等しく、幅優先探索と一致する。深さ優先の3種はいずれも部分木を深く潜ってから戻るため、この並びにはならない。
出典：令和3年度 春期 応用情報技術者試験 午前 問6（IPA）
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。