テクノロジ系
秋期
応用情報技術者 2017年 秋期 問5
5 / 80
配列A[1,A12],・・,Al]で、AIL]を根とし、A間の左側の子をA[21],右側の 子を AL2i+1]とみなすことによって、2分木を表現する。このとき、配列を先頭か ら順に調べていくことは、2分木の探索のどれに当たるか。
正解と解説
表示する
正解 エ
幅優先探索
配列で親をA[i]、子をA[2i]・A[2i+1]として2分木を表すと、配列を先頭から順に読むことは、木を上の階層から同じ深さの左から右へたどる幅優先探索に一致します。行きがけ・帰りがけ・通りがけ順はいずれも深さ優先探索で、たどる順序が異なります。