平成23年度 特別 午前 問6

✓ これが正解エ葉の個数が n ならば，葉以外の節点の個数は n－1 である。

解説

葉が4なら葉以外は3で、小さい木を描けば決まります。

覚えている式を思い出そうとするより、条件を満たす小さい木を一つ描いて四つの記述に当てるほうが確実です。条件は、葉でない節点はすべて子を二つもつこと、そして根から葉までの深さがどの葉でもそろっていることです。深さが2の木を描いてみます。根から二本の枝が下り、その先の節点からもそれぞれ二本の枝が下りて、四つの葉に届きます。このとき葉は4個、葉でない節点は根とその下の2個を合わせて3個、節点の合計は7個、枝は6本です。正解の記述は、葉の個数から1を引いた数が葉でない節点の個数になると述べています。いま描いた木では4から1を引いて3となり、実際の3個と一致します。深さが1の木でも確かめられます。葉は2個、葉でない節点は根だけの1個で、2から1を引いた値と合います。なぜそうなるのかも、木構造の作り方から説明できます。葉でない節点はどれも子を二つもつため、葉でない節点を一つ増やすたびに、その下にぶら下がる葉が一つ分だけ増えていくからです。この型の問いは、深さ1か2の木を紙に描いて当てはめるところまでで終わります。

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

• ア枝の個数が n ならば，葉を含む節点の個…：木では根だけが親をもたないので、枝の本数は節点の個数より必ず一つ少なくなります。深さ2の木でも節点7個に対して枝は6本で、両者は一致しません。
• イ木の深さが n ならば，葉の個数は 2ⁿ…：深さ2の木では葉が4個ありますが、この記述に従うと2の1乗で2個になってしまいます。正しくは2を深さの回数だけ掛けた個数で、指数が一つずれています。
• ウ節点の個数が n ならば，深さは log…：深さ2の木は節点が7個あり、7を2で何回割れるかを考えても深さの2にはなりません。対数で深さが出せるのは節点の総数ではなく葉の個数のほうで、対象が入れ替わっています。