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

解説

正解は4。根をA[1]、A[i]の子をA[2i]とA[2i+1]とすると、深さ0がA[1]、深さ1がA[2]・A[3]、深さ2がA[4]〜A[7]と、深さごとに左から順に添字が並ぶ。配列を先頭から順に調べると、根に近い階層から横方向に調べていくことになり、幅優先探索の順序と一致する。

• 1は、行きがけ順。根→左部分木→右部分木の順なので、A[1]、A[2]の次は左の子A[4]になり、A[3]には進まない。
• 2は、帰りがけ順。左部分木→右部分木→根の順で、根A[1]は最後になる。
• 3は、通りがけ順。左部分木→根→右部分木の順で、先頭は一番左下の節になる。

根拠：2分木の配列表現（ヒープと同じ添字付け）と木の探索順序。