令和3年度 春期 応用情報技術者試験 午前 問6

配列の各要素は、次のように2分木のノードに対応付けられます。

• $A[1]$: 根（深さ0）
• $A[2], A[3]$: 深さ1のノード（根の子）
• $A[4], A[5], A[6], A[7]$: 深さ2のノード

一般に、親ノードのインデックス $i$ に対して左の子が $2i$、右の子が $2i+1$ となる構造では、インデックスが小さい順に同じ深さ（階層）のノードが並ぶことになります。

したがって、配列を先頭（$A[1], A[2], A[3], \dots$）から順に調べるということは、2分木を根から開始して、同じ深さのノードを左から右へ順に訪問していくことに相当します。このように、深さごとに階層レベルで探索を進める手法を 幅優先探索 と呼びます。

各選択肢の解説

• ア：行きがけ順（先行順）深さ優先探索
  「根 $\to$ 左の部分木 $\to$ 右の部分木」の順に深く探索を進めます。配列の先頭から順に調べる順序とは一致しません。
• イ：帰りがけ順（後行順）深さ優先探索
  「左の部分木 $\to$ 右の部分木 $\to$ 根」の順に探索します。根を最後に訪問するため誤りです。
• ウ：通りがけ順（中間順）深さ優先探索
  「左の部分木 $\to$ 根 $\to$ 右の部分木」の順に探索します。配列の先頭から順に調べる順序とは一致しません。
• エ：幅優先探索
  正解です。木を階層順（深さ順）に探索するため、インデックス順に配列を走査する動作に一致します。