図の木構造は２分探索木である。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
図の木構造は２分探索木である。a～g の値の大小関係として，適切なものはどれか。ここで，a～g の値は重複しないものとする。
正解： イ
解説：
２分探索木（Binary Search Tree）の定義は以下のとおりです。
この定義を問題の木に適用します。
ノード a はルートとなるので、各値との関係は以下の通りとなります。
ノード b の部分木では：
よって、ここまでの情報を整理すると d ＜ b ＜ e ＜ a という関係が確定します。
ノード c の部分木では：
これらをまとめると：d ＜ b ＜ e ＜ a ＜ f ＜ c ＜ g となります。
なお，２分探索木には「中間順（通りがけ順）」で巡回すると，値が昇順に取り出せるという性質があります。
中間順（通りがけ順）は以下の順序で値を探索するアルゴリズムです。
この木を中間順に巡回すると d → b → e → a → f → c → g となり，正解と一致します。