基本情報技術者試験 基本情報技術者試験 令和7年度 科目A 公開問題 午前 問3: 図の木構造は２分探索木である。a〜g の値の大小関係として，適切なものはどれか。ここで，a〜g の値は重複しないものとする。

問題本文

図の木構造は２分探索木である。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

正解

イ. d＜b＜e＜a＜f＜c＜g

解説

2分探索木は「任意のノードの左部分木の値 < 自ノードの値 < 右部分木の値」という大小関係を満たします。図の木はaが根で、左部分木にb（左子d・右子e）、右部分木にc（左子f・右子g）を持つので、左→自→右の順（中順走査）で訪問すると値は昇順に並びます。すなわち d＜b＜e＜a＜f＜c＜g となり、選択肢イが正解です。

選択肢ごとの解説

• ア.根のaが先頭にきており、2分探索木の中順走査の順序になっていません。
• イ.中順走査の結果 d＜b＜e＜a＜f＜c＜g と一致しており、2分探索木の大小関係を満たします。
• ウ.葉ノードのd,e,f,gが連続しており、aが最大としていますが、これは2分探索木の構造と矛盾します。
• エ.順序が逆（降順）になっており、aを最大としていますが、aは中央値であるため誤りです。