基本情報技術者試験 令和7年度 科目A 公開問題 問3

【正解】イ

画像では、根がaで、その左の子がb、右の子がcです。また、bの左の子がd、右の子がeであり、cの左の子がf、右の子がgです。2分探索木では、各節について、左部分木の全ての値はその節より小さく、右部分木の全ての値はその節より大きくなります。したがって、bを根とする部分ではd＜b＜e、cを根とする部分ではf＜c＜gです。さらに、aの左部分木にあるd、b、eは全てaより小さく、右部分木にあるf、c、gは全てaより大きいので、全体はd＜b＜e＜a＜f＜c＜gとなります。よって、イが正解です。

アの並びは誤りです。a＜bとなっていますが、bはaの左の子なのでb＜aでなければなりません。また、dはbの左の子なので、b＜dではなくd＜bです。

ウの並びは誤りです。cはaの右の子なのでa＜cでなければなりませんが、示された並びではc＜aとなっています。また、eはbの右の子なのでb＜eでなければなりませんが、e＜bとなっています。

エの並びは誤りです。gはcの右の子なのでc＜g、fはcの左の子なのでf＜cでなければなりません。示されたg＜f＜cは、左右の大小関係と一致しません。

【ポイント】 ・2分探索木は、左の値＜節の値＜右の値という規則を各節で満たします。 ・中間順巡回、すなわち左部分木、節、右部分木の順にたどると、値が昇順に並びます。 ・直接の親子だけでなく、左部分木と右部分木の全体に規則が及ぶ点に注意します。