科目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 |
『情報処理過去問.com』からiPhoneアプリがリリースされました！！
正解
- イ
解説
2分探索木は「左(子)＜中(親)＜右(子)」の制約を持つ木構造です。
2分探索木では，この条件がすべての部分木について成り立つため，
「左部分木 → 親 → 右部分木」の順（中順走査）で節点を列挙すると，常に昇順に並びます。
図の木を中順走査すると
左部分木（d，b，e）→ 根（a）→ 右部分木（f，c，g）となるので，
d → b → e → a → f → c → g
の順に値が小さいことが分かります。
したがって，大きさの関係は
d ＜ b ＜ e ＜ a ＜ f ＜ c ＜ g
よって正解はイです。
2分探索木では，この条件がすべての部分木について成り立つため，
「左部分木 → 親 → 右部分木」の順（中順走査）で節点を列挙すると，常に昇順に並びます。
図の木を中順走査すると
左部分木（d，b，e）→ 根（a）→ 右部分木（f，c，g）となるので，
d → b → e → a → f → c → g
の順に値が小さいことが分かります。
したがって，大きさの関係は
d ＜ b ＜ e ＜ a ＜ f ＜ c ＜ g
よって正解はイです。