正解は「エ」です。
問題文の木は,根から葉までの深さがすべて等しく,葉以外の節点がすべて二つの子をもつので,完全二分木(perfect binary tree)です。深さを d とすると,各レベルの節点数は上から 1,2,4,…,2d となり,次が成り立ちます。
- 葉の個数は 2d
- 葉以外(内部)の節点の個数は 1+2+⋯+2d−1=2d−1
- 節点の総数は 2d+1−1
- ア: 木では一般に「節点の個数 = 枝の個数 + 1」である。葉を含む節点の個数は枝の個数より 1 多いので誤り。
- イ: 深さが n のときの葉の個数は 2n である。2n−1 は誤り。
- ウ: 節点の総数が n のとき,n=2d+1−1 より深さは log2(n+1)−1 となる。log2n は誤り。
- エ: 葉の個数が n=2d のとき,葉以外の節点の個数は 2d−1=n−1 となる。正しい。
よって,正解は「エ」です。