応用情報技術者 2018年秋期午前2 問06

問題文

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

選択肢

ア：枝の個数が

n

ならば、節点の個数も

n

である。

イ：木の深さが

n

ならば、葉の個数は

2^{n - 1}

である。

ウ：節点の個数が

n

ならば、木の深さは

lo g_{2} n

である。

エ：葉の個数が

n

ならば、葉以外の節点の個数は

n - 1

である。（正解）

完全二分木の性質に関する問題【午前2 解説】

要点まとめ

結論：葉の数が $n$ の完全二分木では、葉以外の節点数は必ず $n - 1$ となる。
根拠：完全二分木は葉以外の節点が全て2つの子を持ち、節点数と枝数の関係から導ける。
差がつくポイント：葉の数と内部節点数の関係を正確に理解し、深さや節点数の誤解を避けること。

正解の理由

選択肢エ「葉の個数が

n

ならば、葉以外の節点の個数は

n - 1

である」は、完全二分木の基本的な性質に合致します。
完全二分木では、葉以外の節点はすべて2つの子を持つため、節点数

N

と葉の数

L

の関係は

N = 2 L - 1

となります。
したがって、葉以外の節点数は

N - L = (2 L - 1) - L = L - 1

、すなわち

n - 1

となり正しいです。

よくある誤解

枝の数と節点の数を同じと考えたり、深さの定義を混同して葉の数を誤算することが多いです。
また、深さ

n

の葉の数を

2^{n - 1}

と誤認するケースもありますが、深さの定義に注意が必要です。

解法ステップ

問題文の「葉以外の節点は全て2つの子を持つ」ことを確認する。
完全二分木の節点数と葉の数の関係式を思い出す。
節点数 $N$ は葉の数 $L$ を用いて $N = 2 L - 1$ と表せる。
葉以外の節点数は $N - L = L - 1$ となることを計算する。
選択肢の中でこの関係を満たすものを選ぶ。

選択肢別の誤答解説

ア: 枝の個数が $n$ なら節点数も $n$ とは限らず、枝数は節点数より1少ない。
イ: 深さ $n$ の完全二分木の葉の数は $2^{n}$ であり、 $2^{n - 1}$ は誤り。
ウ: 節点数 $n$ から深さを $lo g_{2} n$ とするのは近似的であり、正確ではない。
エ: 葉の数 $n$ に対し葉以外の節点数が $n - 1$ で正しい。

補足コラム

完全二分木は「すべての葉が同じ深さで、葉以外の節点が2つの子を持つ」木構造です。
節点数

N

、葉の数

L

、枝の数

E

は以下の関係が成り立ちます。

N = 2 L - 1, E = N - 1 = 2 L - 2

この性質はデータ構造やアルゴリズムの理解に役立ちます。

FAQ

Q: 完全二分木の深さはどう定義されますか？
A: 根から葉までの枝の数で定義し、すべての葉が同じ深さを持ちます。

Q: なぜ節点数は

2 L - 1

になるのですか？
A: 葉以外の節点は2つの子を持つため、節点数と葉の数の関係から導かれます。

関連キーワード: 完全二分木、節点数、葉の数、木の深さ、データ構造、二分木

← 前の問題へ次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2018年 秋期 午前2 問06

問題文

選択肢

完全二分木の性質に関する問題【午前2 解説】

要点まとめ

正解の理由

よくある誤解

解法ステップ

選択肢別の誤答解説

補足コラム

FAQ

応用情報技術者 2018年秋期午前2 問06