アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20110702 実施分 問5
2分探索木として適切なものはどれか。ここで，1～9の数字は，各ノード（節）の値を表す。
ア〜エの4つの2分木の図（各ノードは丸の中に数字）。
ア: 1─(左)2─(左)4,(右)5／1─(右)3─(左)6─(左)8,(右)9／3─(右)7
イ: 4─(左)2─(左)1,(右)3／4─(右)8─(左)6─(左)5,(右)7／8─(右)9
ウ: 7─(左)6─(左)4,(右)5／7─(右)8─(左)3─(左)1,(右)2／8─(右)9
エ: 9─(左)7─(左)1,(右)2／9─(右)8─(左)5─(左)3,(右)4／8─(右)6
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20110702 実施分 問5（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：イ
覚える知識
2分探索木の大小関係
2分探索木では、任意の節点について左部分木の全値は節点値より小さく、右部分木の全値は大きい。
この問題で必要なこと
2分探索木は各節点で左部分木の値が節点より小さく、右部分木の値が大きい。イは全節点でこの条件を満たす。
ひっかけ
根だけでなく深い階層の子にも条件が及ぶ点を見落とすと、一部だけ満たす図を選んでしまう。
この知識の出題：本試験系 4 回・免除試験 8 回（公開問題での観測値）