平成26年度 秋期 応用情報技術者試験 午前 問4

この表現では，A[1] が根（深さ0），A[2]，A[3] が深さ1，A[4]～A[7] が深さ2，… というように，配列の添字の順番は「根に近い階層から順に，同じ階層では左から右へ」並びます。配列を先頭から順に調べることは，木を階層ごとに左から右へたどることになります。

• ア: 行きがけ順（先行順）深さ優先探索
  誤り。行きがけ順では，根→左部分木→右部分木の順にたどるので，A[1]，A[2]，A[4]，… の順になり，配列の先頭からの順番と一致しません。

• イ: 帰りがけ順（後行順）深さ優先探索
  誤り。帰りがけ順では，左部分木→右部分木→根の順にたどるので，根である A[1] が最後になり，配列の順番と一致しません。

• ウ: 通りがけ順（中間順）深さ優先探索
  誤り。通りがけ順では，左部分木→根→右部分木の順にたどるので，最も左の葉から始まり，配列の順番と一致しません。

• エ: 幅優先探索
  正しい。幅優先探索は，根から近い階層順に，同じ階層では左から右へとたどる方法で，配列を先頭から順に調べる順番と一致します。

答え

エ: 幅優先探索