葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木を考える。
この木に関する記述のうち、適切なものはどれか。
ここで、深さとは根から葉に至るまでの枝の個数を表す。
| ア | 枝の個数がn ならば、葉を含む節点の個数もn である。 |
| イ | 木の深さがn ならば、葉の個数は2n -1である。 |
| ウ | 節点の個数がn ならば、深さはlog2n である。 |
| エ | 葉の個数がn ならば、葉以外の節点の個数はn -1である。 |
答え エ
【解説】
完全二分木の図で確認しながら、選択肢を確認する。
| ア | 根以外のすべての節点には親とつながるための枝を持っているので、枝の個数が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である。 |
【キーワード】
・二分木
- 二分木(binary tree、バイナリツリー)
二分木はコンピュータで扱うデータ構造の一つで、1つのデータ(親)が左と右の2つの子データを持つ。
(二分木)
親データから見て、左の子データは自分より小さいデータ、右の子データは大きいデータと整理することで、データの探索などを容易に行えるようになる。
二分木データのうち、問題にある「葉以外の節点はすべて二つの子を持ち、根から浜での深さがすべて等しい木」を『完全二分木』という。
(完全二分木)
もっと、「二分木」について調べてみよう。
戻る
一覧へ
次へ