平成15年春期試験問題 午前問12

問12解説へ
10個の節(ノード)からなる次の2分木の各節に,1から10までの値を一意に対応するように割り振ったとき,節a,bの値の組合せはどれになるか。ここで,各節に割り振る値は,左の子及びその子孫に割り振る値より大きく,右の子及びその子孫に割り振る値より小さくする。

- a=6,b=7
- a=6,b=8
- a=7,b=8
- a=7,b=9
広告
解説
問題文中の「各節に割り振る値は,左の子及びその子孫に割り振る値より大きく,右の子及びその子孫に割り振る値より小さくする」というのは、「左の子の値<親の値<右の子の値」になるように割り振ればよいということです。つまり、左端が最小値、右端が最大値です。
節aの値は、5より大きく、上の図の赤の部分内の3つの値より小さくなります。
節bの値は、上の図の赤の部分内の3つの値より小さくなるので、節bの値は7です。
したがって、節aの値は6です。

節bの値は、上の図の赤の部分内の3つの値より小さくなるので、節bの値は7です。
したがって、節aの値は6です。
広告