修了試験 2020-06-14実施分 基本情報技術者試験 問7

解説

正解は2です。 2分探索木の条件を問う問題です。 2分探索木では、どのノードについても「左部分木の値＜そのノードの値＜右部分木の値」が成り立ちます。 図の4つの木について、根から順にこの条件を確かめます。 【選択肢別解説】 1：× 選択肢1（図のア）は根が1で、左の子が2です。 左部分木に根より大きい値があるので、2分探索木の条件を満たしません。 2：○ 選択肢2（図のイ）は根が4で、左部分木は2、1、3、右部分木は8、6、9、5、7です。 2の左に1、右に3があります。 8の左に6、右に9があり、6の左に5、右に7があります。 すべてのノードで「左＜親＜右」が成り立つので、2分探索木です。 3：× 選択肢3（図のウ）は根が7で、右部分木に3、1、2が含まれています。 右部分木に根より小さい値があるので、条件を満たしません。 4：× 選択肢4（図のエ）は根が9で、右の子が8です。 右部分木に根より小さい値があるので、条件を満たしません。 【ポイント】 2分探索木を中間順（左、根、右の順）でたどると、値が昇順に並びます。 選択肢2の木を中間順にたどると1、2、3、4、5、6、7、8、9となり、確認に使えます。