2分探索木の大小関係
図の木構造は 2 分探索木である。a~g の値の大小関係として,適切なものはどれか。ここで,a~g の値は重複しないものとする。

- A
a<b<d<e<c<f<g
- B
d<b<e<a<f<c<g
- C
d<e<f<g<b<c<a
- D
g<f<c<e<d<b<a
正解と解説を見る
正解:B
2分探索木を中間順になぞると昇順の列が得られる。この木ではd, b, e, a, f, c, gの順になる。
出典: 令和7年度 基本情報技術者試験 科目A 公開問題 問3(IPA 独立行政法人情報処理推進機構)。図・表は公開問題の画像を切り出して使用。解説はこのサイトが作成。
- A
誤り。aが最小になっているが、2分探索木ではaの左部分木(b, d, e)がすべてaより小さくなければならない。
- B
正しい。2分探索木では「左部分木<節<右部分木」が成り立つ。根aの左にb(その左d・右e)、右にc(その左f・右g)があるので、中間順(左→節→右)に並べるとd<b<e<a<f<c<gとなる。
- C
誤り。aが最大になっているが、右部分木のc, f, gはaより大きくなければならない。
- D
誤り。大小が逆である。左の子は親より小さいのでd<b、b<aでなければならない。
このサイトの問題は、公開されている出題範囲に沿って作ったオリジナルの模擬問題です。本試験の問題ではありません。独立行政法人情報処理推進機構(IPA)の公式サービスではありません。