平成28年度 春期 基本情報技術者試験 午前 問5
テクノロジ／アルゴリズム10個の節（ノード）から成る次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節a，bの値の組合せはどれになるか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値よりも大きく，右の子及びその子孫に割り振る値よりも小さくするものとする。
出典：平成28年度 春期 基本情報技術者試験 午前 問5
- アa=6，b=7
- イa=6，b=8
- ウa=7，b=8
- エa=7，b=9
正解：ア
解説
各節の値が左部分木の値より大きく右部分木の値より小さいという規則は，二分探索木の性質そのものであり，木を中間順（in-order：左，節，右の順）に走査すると値がちょうど1から10まで昇順に並ぶことを意味します。図の木を中間順に走査すると，4の左下の葉，その親，4の右下の葉，4，根（5），a，b，bの親，その右の子，一番右下の葉という順になり，これに1から10を割り当てるとa＝6，b＝7になります。
選択肢ごとの解説
- ア正しい。中間順走査でa，bはそれぞれ6番目，7番目の値になります。
- イ誤り。bをaより2大きい値と誤認した場合の組合せです。実際にはbはaの次の値（7）になります。
- ウ誤り。根の値5を数え方から外すなどして，1つずつ大きい値を割り当ててしまった場合の組合せです。
- エ誤り。aとbの位置を中間順の並びで2つ分ずらして数えた場合の組合せです。