配列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というように、同じ深さのノードが配列上で連続して並ぶ。したがって配列を先頭から順に調べることは、根に近い階層から順に、各階層内は左から右へ辿ることを意味し、幅優先探索に相当する。

選択肢ごとの解説

• ア行きがけ順は根を訪問してから左部分木、右部分木と深く潜る順序。
• イ帰りがけ順は左右の部分木を処理し終えてから根を訪問する順序。
• ウ通りがけ順は左部分木、根、右部分木の順に訪問する順序。
• エ正しい。配列の並び順は木の階層順（レベル順）と一致する。

同じ分野の他の問題

• 図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。2025年度 春期 午前 問6
• A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データ…2016年度 春期 午前 問5
• 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
• 各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたと…2024年度 春期 午前 問6
• 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5