令和7年度 科目A 問3

✓ これが正解イd＜b＜e＜a＜f＜c＜g

解説

左の子は親より小さく右の子は大きいので、d＜b＜e＜a＜f＜c＜g です。

2分探索木では、どの節点についても、左の部分木にある値はその節点より小さく、右の部分木にある値はその節点より大きくなるように値を置きます。この図の根は a で、左に b を根とする部分木、右に c を根とする部分木があります。b の下では d が左、e が右なので d＜b＜e、c の下では f が左、g が右なので f＜c＜g です。さらに b の側の値はすべて a より小さく、c の側の値はすべて a より大きいので、全体は d＜b＜e＜a＜f＜c＜g となります。左の部分木、節点、右の部分木の順にたどる中間順で読むと、2分探索木の値は小さい順に並ぶ、と覚えておくと一度で書き出せます。

ほかの選択肢はなぜ違うのか

• アa＜b＜d＜e＜c＜f＜g：根の a を最小に置き、そのあと b、d、e と上の節点から順に並べています。2分探索木では左の子は親より小さいので、b は a より小さく、d は b より小さくなければならず、根を最小とするこの並びは成り立ちません。
• ウd＜e＜f＜g＜b＜c＜a：d、e、f、g の葉を先に、その上の b と c、最後に根の a と、段ごとに下から並べています。木の深さで並べただけで大小の規則を使っておらず、e は b の右の子なので b より大きいはずなのに、b より小さく置かれています。
• エg＜f＜c＜e＜d＜b＜a：g から a へと大きくなる並びで、左右の大小の向きが逆になっています。g は c の右の子なので c より大きいはずなのに最小に置かれており、左は小さく右は大きいという規則と合いません。