木の巡回（走査）とは？きのじゅんかい
木の巡回（走査）とは、木構造の全節点を規則に沿って一度ずつ訪問すること。二分木では、節点を左右の部分木より先に処理する行きがけ順（前順）、左・節点・右の順に処理する通りがけ順（中順）、左右の部分木のあと最後に節点を処理する帰りがけ順（後順）の3通りがあり、目的に応じて選ぶ。
最終更新：2026-10-06
この語が出る過去問を解く →背景
木は親子関係だけを持つ構造で、配列のような「先頭から順に」という自然な並びを持たない。ところが探索・出力・式の評価は、いずれ節点を一列に並べて処理することになる。巡回順序は、木という枝分かれした構造を1次元の処理順へ落とすための規則であり、どれを選ぶかで得られる結果そのものが変わるため、目的から逆算して選ぶ必要がある。
具体例
数式を表す2分木を通りがけ順に巡回すると中置記法、帰りがけ順に巡回すると後置記法（逆ポーランド記法）が得られ、後置記法はスタックだけで評価できる。2分探索木を通りがけ順に巡回すれば、値がそのまま昇順に並んで出てくる。
試験での引っ掛け
3つの順序は、節点自身を処理する位置が左右の部分木の前・間・後のどこかで決まる。左右の訪問順は常に左が先で、これを入れ替えた選択肢が誤り。深さ優先はスタックまたは再帰、幅優先はキューで実装するという対応関係も併せて問われる。
関連用語
出た過去問
出典：平成29年度 秋期 応用情報技術者試験 午前 問5（IPA）
配列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というように、同じ深さのノードが配列上で連続して並ぶ。したがって配列を先頭から順に調べることは、根に近い階層から順に、各階層内は左から右へ辿ることを意味し、幅優先探索に相当する。
出典：令和3年度 春期 応用情報技術者試験 午前 問6（IPA）
配列A[1]，A[2]，…，A[n]で、A[1]を根とし、A[i]の左側の子をA[2i]、右側の子をA[2i+1]とみなすことによって、2分木を表現する。このと…
正解：幅優先探索
要点：ヒープ形式の配列表現の添字順は幅優先の訪問順
この配列表現では、添字の小さい順に根、深さ1の全ノード、深さ2の全ノード…と並ぶ。したがって配列を先頭から順に走査することは、根から始めて同じ深さのノードを左から右へ順に訪問することに等しく、幅優先探索と一致する。深さ優先の3種はいずれも部分木を深く潜ってから戻るため、この並びにはならない。
出典・参考
公式シラバスの1 基礎理論 ＞ 1. データ構造 ＞ (2) データ構造の種類に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。