問5応用情報技術者 平成29年度 秋期

解説

正解は4。A[i]の子をA[2i]、A[2i+1]に置くと、根A[1]が深さ0、A[2]〜A[3]が深さ1、A[4]〜A[7]が深さ2…と、添字の順に浅い階層から左から右へ並ぶ。配列を先頭から順に調べることは、根から近い階層を一段ずつ調べる幅優先探索と同じ順序になる。

• 1は、行きがけ順は親→左の部分木→右の部分木の順で、A[1]、A[2]、A[4]…と深く潜るので添字順にならない。
• 2は、帰りがけ順は左右の子を先に訪れて親を最後にするので、根A[1]が最後になる。
• 3は、通りがけ順は左の部分木→親→右の部分木で、最初に訪れるのは最も左下のノード。

根拠：二分木の配列表現（ヒープの格納方法）と探索順序の定義。