葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。

選択肢

• ア枝の個数がnならば，節点の個数もnである。
• イ木の深さがnならば，葉の個数は2^(n-1)である。
• ウ節点の個数がnならば，木の深さはlog2 nである。
• エ葉の個数がnならば，葉以外の節点の個数はn-1である。

正解と解説

正解：エ 葉の個数がnならば，葉以外の節点の個数はn-1である。

葉以外がすべて2つの子をもち、根から各葉までの深さが等しい木（完全な2分木）では、深さnのとき葉は2^n個、節点の総数は2^(n+1)−1個になる。ここで、葉がn個であれば葉以外（内部節点）は必ずn−1個になる。これは節点総数が2n−1で、そこから葉のn個を引くと得られる関係である。

選択肢ごとの解説

• ア節点の個数は枝の個数より必ず1多く、n個の枝ならn+1個の節点になる。
• イ深さnのときの葉は2^n個であり、2^(n−1)個ではない。
• ウ節点n個のとき深さはlog2(n+1)−1であり、log2 nにはならない。
• エ正しい。葉がn個なら内部節点は必ずn−1個になる。

同じ分野の他の問題

• 図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。2025年度 春期 午前 問6
• A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データ…2016年度 春期 午前 問5
• 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
• 各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたと…2024年度 春期 午前 問6
• 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5