応用情報技術者試験 令和3年春 午前問6 解説付き過去問
問題
配列A[1]、A[2]、･･･、A[n]で、A[1]を根とし、A[i]の左側の子をA[2i]、右側の子をA[2i+1]とみなすことによって、2分木を表現する。
このとき、配列を先頭から順に調べていくことは、2分木の探索のどれに当たるか。
正解
解説
この問題は、配列を使用して2分木を表現する方法と、その探索方法がどの木のトラバーサル方法に対応するかを理解することが求められます。
- 2分木の配列表現
配列による2分木の表現では、配列のインデックスを利用して、各要素がノードの役割を果たします。根元素はA[1]で、任意の要素A[i]について、左の子ノードはA[2i]、右の子ノードはA[2i+1]に位置します。ただし、これは2iと2i+1が配列の長さnを超えない場合に限ります。 - 配列の順番と2分木の探索
配列を先頭から順に調べるという操作は、2分木の各レベルを左から右へと順に訪れることと等価です。例えば、最初の要素から順に見ていくと、根（A[1]）、その次に根の子ノード（A[2], A[3]）、その次にそれらの子ノード（A[4], A[5], A[6], A[7]）という順になり、これは2分木のレベル毎に横断していく幅優先探索（Breadth-First Search, BFS）に相当します。
したがって、配列を先頭から順に調べることは、2分木における幅優先探索に当たります。