基本情報技術者試験 平成31年度 春期 午前 問5
2 分探索木の条件と探し方についての問題。
--------------------------
平成31年度 春期 午前 問5
２分探索木として適切なものはどれか。ここで、数字１〜９は、各ノード（節）の値を表す。
--------------------------
解説
四択の図を文章で表すスキルはないので手書きにて。
きれいな円（丸）はどうやったら書けるようになるのか。
２分探索木とは何か。
「左の子（枝）の値 ≦ 親の値 ≦ 右の子（枝）の値」
を満たす２分木のこと。
では２分木とは何か。
「データ構造の一種。木構造のなかで各ノード（節）がもつ子の数が高々２であるもの」
"高々2 " という言い回しは "多くても２" や "2 以下" と同じ。英語だと at most。
例として問題の選択肢アをみると、①のノードは②と③を子（枝）としてもっている。
②のノードは④と⑤を子（枝）としてもっている。
全てのノードをみたときに、もっている子（枝）の数がこの様に常に 2 以下であれば 2 分木ということになる。
木とか枝という表現を使っているが、下向きに枝が伸びているようなイメージになっていることに注意。
問題の選択肢の中でこの条件を満たしていないものはないので、全て 2 分木ではあることになる。
なので、これら 2 分木の中から 2 分探索木の条件である
「左の子（枝）の値 ≦ 親の値 ≦ 右の子（枝）の値」
を満たす選択肢をさがせば良い。
選択肢アは一番上の①を親として見ると、
左の子② ≦ 親① ≦ 右の子③
となるので不等号の向きがおかしくなる。
選択肢ウは左側の⑥を親として見ると、
左の子④ ≦ 親⑥ ≦ 右の子⑤
となるので不等号の向きがおかしくなる。
選択肢エは一番上の⑨を親として見ると、
左の子⑦ ≦ 親⑨ ≦ 右の子⑧
となるので不等号の向きがおかしくなる。
選択肢イはどのノードをみても 2 分探索木の条件を満たしているので、正解は選択肢イとなる。
2 分探索木を探す問題における他の解き方として、下図の様に反時計回りで木構造に沿う様に曲線を引く方法がある。
Start（最初のノードの上側）から曲線を引き、曲線が真下を通る順番でノード（節）の値を並べてみる。
このとき正しい２分探索木であれば値が小さい順に並ぶ。
図は正解である選択肢イに対して曲線を描いたものであるが、曲線が真下を通るノードを順番に見ると 1,2,3,4,5,6,7,8,9 ときれいに並んでいる。
木構造がこの問題の選択肢よりもっと大きく、条件を満たさない親子の箇所が見つけにくい時はこちらの方が早いかもしれない。
前後の問題はこちら。
