基本情報技術者試験過去問 令和7年度（2025年）科目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
- ア
- イ
- ウ
- エ
正解と解き方・学習ポイント（AI解説）
2分探索木は、各ノードについて「左部分木の値はそのノードより小さい」「右部分木の値はそのノードより大きい」という規則を満たします。この木を中間順走査（左部分木→自分→右部分木）でたどると、値は小さい順に並びます。図では d, b, e, a, f, c, g の順になるため、大小関係は d＜b＜e＜a＜f＜c＜g となり、正解は「イ」です。
Point
この問題は、2分探索木の規則を根だけでなく各部分木にも適用できることと、中間順走査（左→根→右）が昇順になることを用いて、図から値の大小関係を確定できるかを確認するものです。
解くために必要な知識
この問題を解くには、2分探索木（BST）の性質（左部分木＜親＜右部分木）の理解が必要です。
用語の整理
| 用語名 | 意味 |
|---|---|
| 2分探索木（BST） | 各ノードで左部分木の値＜ノードの値＜右部分木の値を満たす2分木です。同じ規則が部分木にも成り立ちます。 |
| 根（root） | 木構造の最上位のノードです。 |
| 部分木 | あるノードを根として、その配下にあるノード全体からなる木です。 |
図表の読み取り方
基本規則
-
親ノードを基準に、左側にあるノード群はすべて親より小さいです。
-
親ノードを基準に、右側にあるノード群はすべて親より大きいです。
重要な点
-
規則は子だけでなく部分木全体に適用します。
-
例えば、あるノードが親の左部分木にあるなら、そのノードは親より小さい値です。
解くための手順
手順
-
図から、各ノードの左の子と右の子を確認します。
-
根から中間順走査（左→自分→右）を行います。
-
得られた訪問順を、値の昇順（＜でつないだ順）として選択肢と照合します。
選択肢ごとの解説
- ア：不正解
aをbより小さい（a＜b）としていますが、2分探索木ではaの左部分木（b,d,e）はaより小さい必要があります。よって誤りです。
- イ：正解
図よりb＜a＜c、d＜b＜e、f＜c＜gが成り立ちます。またa＜cなので、cの左部分木にあるfはaより大きくa＜fです。よってd＜b＜e＜a＜f＜c＜gとなり、選択肢と一致しますので正解です。
- ウ：不正解
bがgより大きい（g＜b）としていますが、gはaの右部分木にあり、bはaの左部分木にあります。左部分木の値は右部分木の値より小さくなるため矛盾し、誤りです。
- エ：不正解
g＜fとしており、cの部分木で必要な関係（f＜c＜g）のうちf＜gに反します。よって誤りです。
まとめ
2分探索木は、各ノードについて「左部分木の値はそのノードより小さい」「右部分木の値はそのノードより大きい」という規則を満たします。この木を中間順走査（左部分木→自分→右部分木）でたどると、値は小さい順に並びます。図では d, b, e, a, f, c, g の順になるため、大小関係は d＜b＜e＜a＜f＜c＜g となり、正解は「イ」です。
aをbより小さい（a＜b）としていますが、2分探索木ではaの左部分木（b,d,e）はaより小さい必要があります。よって誤りです。
図よりb＜a＜c、d＜b＜e、f＜c＜gが成り立ちます。またa＜cなので、cの左部分木にあるfはaより大きくa＜fです。よってd＜b＜e＜a＜f＜c＜gとなり、選択肢と一致しますので正解です。
bがgより大きい（g＜b）としていますが、gはaの右部分木にあり、bはaの左部分木にあります。左部分木の値は右部分木の値より小さくなるため矛盾し、誤りです。
g＜fとしており、cの部分木で必要な関係（f＜c＜g）のうちf＜gに反します。よって誤りです。