問6応用情報技術者 平成30年度 秋期

解説

正解は4。この木は葉以外が必ず2つの子をもつ完全な2分木。深さ1なら葉2・葉以外1、深さ2なら葉4・葉以外3、深さnなら葉2ⁿ、葉以外は1＋2＋…＋2ⁿ⁻¹＝2ⁿ−1。葉の数をnと置けば葉以外はn−1になる。

• 1は、木では枝の数は節点の数より1少ない。深さ1なら節点3、枝2。
• 2は、深さnの葉の数は2ⁿ。深さ1で葉2個なので2ⁿ⁻¹（＝1）は合わない。
• 3は、節点の個数は2ⁿ⁺¹−1なので、節点数nに対する深さはlog₂(n＋1)−1。深さ1（節点3）でlog₂3は整数にもならない。

根拠：2分木の節点数・葉の数・枝の数の関係。