データ構造(全52問中14問目)
No.14解説へ
10個の節(ノード)からなる次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節a，bの値の組合せはどれになるか。ここで，各節に割り振る値は，左の子及びその子孫に割り振る値より大きく，右の子及びその子孫に割り振る値より小さくする。
出典：平成28年春期 問 5
- a＝6，b＝7
- a＝6，b＝8
- a＝7，b＝8
- a＝7，b＝9
広告
解説
問題文中の「各節に割り振る値は，左の子及びその子孫に割り振る値より大きく，右の子及びその子孫に割り振る値より小さくする」というのは、「左の子の値＜親の値＜右の子の値」になるように割り振ればよいということです。つまり、左端が最小値、右端が最大値です。
左部分木の空白になっている3つの節には、それぞれ4より小さい値が入るので「3，2，1」が入ることになります。残る数字は「6，7，8，9，10」の５つですが、問題の大小関係を満たすためには節aの値に、5より大きく、残る５つの数字の中で最も小さい値が入る必要があるため節a＝6が適切です。また節bの値は、「左の子の値＜親の値＜右の子の値」という条件から考えると、残る4つの数字の中で最も小さい7が収まることになります。
したがってa＝6，b＝7が正解です。
左部分木の空白になっている3つの節には、それぞれ4より小さい値が入るので「3，2，1」が入ることになります。残る数字は「6，7，8，9，10」の５つですが、問題の大小関係を満たすためには節aの値に、5より大きく、残る５つの数字の中で最も小さい値が入る必要があるため節a＝6が適切です。また節bの値は、「左の子の値＜親の値＜右の子の値」という条件から考えると、残る4つの数字の中で最も小さい7が収まることになります。
したがってa＝6，b＝7が正解です。
広告