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

正解 エ

配列を先頭から順に見ると、根から深さごとに左から右へ節を訪れます。これは幅優先探索の順序です。

A[1] が根で、A[i] の子は A[2i] と A[2i+1] です。この表し方では、深さ1の節が A[2]、A[3]、深さ2の節が A[4]〜A[7] のように並びます。つまり配列には、同じ深さの節が左から右の順に、浅い段から順に入っています。そのため A[1]、A[2]、A[3]、…と順に調べると、根に近い段から1段ずつ横に調べる幅優先探索になります。

ア：行きがけ順は、節、左部分木、右部分木の順に訪れる深さ優先探索です。A[1]、A[2]、A[4]、…となり、配列の順になりません。

イ：帰りがけ順は、左部分木、右部分木、節の順に訪れる深さ優先探索です。根の A[1] が最後になり、配列の順になりません。

ウ：通りがけ順は、左部分木、節、右部分木の順に訪れる深さ優先探索です。一番左の葉から始まり、配列の順になりません。

出典：平成26年度 秋期 応用情報技術者試験 問4