配列で表した 2 分木を先頭から調べる順序
出典: 平成29年度 秋期 応用情報技術者試験 午前 問5 (IPA)
配列 A[1]，A[2]，…，A[n] で，A[1] を根とし，A[i] の左側の子を A[2i]，右側の子を A[2i＋1] とみなすことによって，2 分木を表現する。このとき，配列を先頭から順に調べていくことは，2 分木の探索のどれに当たるか。
- ア 行きがけ順（先行順）深さ優先探索
- イ 帰りがけ順（後行順）深さ優先探索
- ウ 通りがけ順（中間順）深さ優先探索
- エ 幅優先探索
正解と解説を見る
正解: エ
- ア: 行きがけ順は、根 → 左の部分木 → 右の部分木の順に深く進むので、A[1]，A[2]，A[4]，… の順になります。
- イ: 帰りがけ順は、左の部分木 → 右の部分木 → 根の順なので、根が最後になります。
- ウ: 通りがけ順は、左の部分木 → 根 → 右の部分木の順です。
- エ: 配列を先頭から調べると、浅い段から順に左から右へ調べることになるので幅優先探索です。正しい答えです。
ポイント
- A[1] が根、A[2]，A[3] がその子、A[4]〜A[7] が孫、… と並んでいます。
- 配列を先頭から順に見ると、根 → 深さ 1 のノード (左から) → 深さ 2 のノード (左から) … と、浅い段から 1 段ずつ調べることになります。これは 幅優先探索 です。