平成28年度 秋期 基本情報技術者試験 午前 問6

解説

2分探索木は，各ノードについて，左部分木の全ての値がそのノードの値より小さく，右部分木の全ての値がそのノードの値より大きいという条件を満たす2分木です。この条件を全てのノードで確認し，満たしているものを選びます。

選択肢ごとの解説

• ア誤り。根16の左部分木にある15の右の子14は，右の子として15より大きい値でなければならないところ15より小さく，条件に違反しています。
• イ正しい。根17に対し，左部分木（14，10，16）は全て17未満，右部分木（19，18）は全て17より大きく，14や19の左右の子についても大小関係が正しく成り立っています。
• ウ誤り。根18の左部分木にある16の右の子14は，右の子として16より大きい値でなければならないところ16より小さく，条件に違反しています。
• エ誤り。根20の右の子19は，右部分木として20より大きい値でなければならないところ20より小さく，根の時点で条件に違反しています。