2分探索木になっている2分木はどれか。

選択肢

• ア根16、左の子15（左の子10、右の子14）、右の子19。
• イ根17、左の子14（左の子10、右の子16）、右の子19（左の子18）。
• ウ根18、左の子16（左の子15、右の子14）、右の子19（右の子20）。
• エ根20、左の子18（左の子10、右の子14）、右の子19（左の子15、右の子16）。

正解と解説

正解：イ 根17、左の子14（左の子10、右の子16）、右の子19（左の子18）。

2分探索木は、任意の節点について左部分木のすべての値がその節点より小さく、右部分木のすべての値が大きいという条件を満たす木である。根17に対し左側が10・14・16、右側が18・19となり、さらに14の左が10・右が16、19の左が18と、どの節点でも条件が崩れていない木が正解となる。

選択肢ごとの解説

• ア節点15の右の子が14であり、右の子が親より小さくなっていて条件を満たさない。
• イどの節点でも左＜親＜右が成り立っており、2分探索木の条件を満たす。これが正解。
• ウ節点16の右の子が14になっており、大小関係が逆転している。
• エ根20の右部分木に15や16という根より小さい値が含まれており、部分木全体の条件に反する。

この問題に出た用語

• 2分探索木
• 2分探索

同じ分野の他の問題

• 次のプログラム中の a と b に入れる正しい答えの組合せを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。…2026年度 公開問題 科目B 問4
• 次のプログラム中の a と b に入れる正しい答えの組合せを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。…2025年度 公開問題 科目B 問3
• 図の木構造は2分探索木である。a〜gの値の大小関係として，適切なものはどれか。ここで，a〜gの値は重複しないものとする。2025年度 公開問題 科目A 問3
• 次のプログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 図1に示すグラフの…2024年度 公開問題 科目B 問3
• 双方向のポインタをもつリスト構造のデータを表に示す。この表において新たな社員Gを社員Aと社員Kの間に追加する。追加後の表…2023年度 公開問題 科目A 問2