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

科目A　科目A 問3

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

アa ＜ b ＜ d ＜ e ＜ c ＜ f ＜ g
イd ＜ b ＜ e ＜ a ＜ f ＜ c ＜ g
ウd ＜ e ＜ f ＜ g ＜ b ＜ c ＜ a
エg ＜ f ＜ c ＜ e ＜ d ＜ b ＜ a

正答イ

正答はイ。2分探索木を中間順になぞった順番が、小さい順です。 2分探索木では、どの節でも「左の部分木の値＜節の値＜右の部分木の値」が成り立ちます。図の木に当てはめると、 b の下　d ＜ b ＜ e c の下　f ＜ c ＜ g a の下　左の部分木（d，b，e）＜ a ＜右の部分木（f，c，g）これらをつなぐと、d ＜ b ＜ e ＜ a ＜ f ＜ c ＜ g となります。これは、左の部分木→節→右の部分木の順に巡る、中間順（間順）の走査の順番と同じです。【ほかの選択肢】

解説の続きをみる続きを閉じる

ア a ＜ b ＜ d ＜ e ＜ c ＜ f ＜ g　誤り　　→ 根の a を最小にしている。a は左の部分木の b，d，e より大きいウ d ＜ e ＜ f ＜ g ＜ b ＜ c ＜ a　誤り　　→ 葉を先に並べている。b は e より小さく、a は f より小さいエ g ＜ f ＜ c ＜ e ＜ d ＜ b ＜ a　誤り　　→ 大小が逆。右の部分木の右端の g が最大になる【覚え方】 2分探索木の最小値は左端、最大値は右端の節です。中間順に走査すると、値が昇順に取り出せます。

出典：令和7年度基本情報技術者試験科目A 公開問題問3（独立行政法人情報処理推進機構）出典元ページ

最終更新日 2026年10月14日

この回を通しで解くこの分野を年度横断で解く

「科目A」のほかの問題

問題文・解答の修正依頼