答え エ
【解説】
完全二分木の図で確認しながら、選択肢を確認する。
ア |
根以外のすべての節点には親とつながるための枝を持っているので、枝の個数がn ならば、節点の個数はn +1である。(+1は根。) |
イ |
木の深さが1(親と子のみ)ならば葉の数は2(=21)、木の深さが2(親と子、孫)ならば葉の数は4(=22)であり、木の深さがn ならば葉の数は2n である。 |
ウ |
木の深さが1(親と子のみ)ならば節の数は3(=1+2)、木の深さが2(親と子、孫)ならば節の数は7(=1+2+4)、木の深さが3ならば節の数は15(=1+2+4+8)であり、木の深さがn ならば節の数は2n +1-1であり、選択肢の条件は成立しない。(なお、葉の個数がn ならば、木の深さはlog2n である。) |
エ |
葉の数が2(木の深さが1)のとき葉以外の節の個数は1(根のみ)であり、葉の数が4(木の深さが2)のとき葉以外の節の個数は3(=1+2)、葉の数が8(木の深さが3)のとき葉以外の節の個数は7(=1+2+4)であり、葉の数がn ならば葉以外の節の個数はn -1である。 |