基本情報技術者試験 基本情報技術者試験 平成31年度 春期 午前 午前 問5: 2分探索木として適切なものはどれか。ここで，数字 1〜9 は，各ノード（節）の値を表す。

正解

イ. 図イ: 根=4、左部分木 = {2 を根とし 1,3 を子}、右部分木 = {8 を根とし 6,9 を子、6 の子に 5,7}。全ノードで左<親<右が成立する正しい二分探索木。

正答率 61.5%（1,709人中 1,051人が正解）

問題の解説

2分探索木の条件は「左部分木の全ノード < 親 < 右部分木の全ノード」。イ (根=4、左部分木 [2:{1,3}]、右部分木 [8:{6:{5,7}, 9}]) は全ノードでこの条件を満たす。イが正解。

選択肢ごとの解説

• ア根=1 の右に 2,3 を配置 (1<2,1<3 OK) だが、その下に 4-9 を配置する構造で条件が成立しない箇所がある。
• イ根=4、左=2(<4)、右=8(4)、各部分木でも順序が保たれる。2分探索木の条件を満たし正解。
• ウ根=7、左=6(<7)、右=8(7) は OK だが、左部分木の下に 4,5,3 配置で順序矛盾がある。
• エ根=9、左=7(<9)、右=8(9 でない) — 右部分木の値が根より小さく矛盾。