節点の集合が{1, 2, …, n }である木を表現するために、大きさn の整数型配列A[1], A[2], …, A[n ]を用意して、節点i の親の節点をA[i ]に格納する。
節点k が根の場合はA[k ]=0とする。
表に示す配列が表す木の葉の数は、幾つか。
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
A[i ] |
0 |
1 |
1 |
3 |
3 |
5 |
5 |
5 |
答え ウ
【解説】
表を示す配列
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
A[i ] |
0 |
1 |
1 |
3 |
3 |
5 |
5 |
5 |
から、1が根で、2と3の親が1、4と5の親が3、6と7と8の親が5であるので、これを図にすると

になる。
これで、葉を数えると、葉は子のない要素なので2、4、6、7、8の 5個(ウ)である。
【キーワード】
・木
【キーワードの解説】
- 木(木構造)
グラフの一種で、グラフの木を使ったデータ構造が木構造である。
通常は親を持たない根と、親と子を持つ節点、子を持たない葉とそれを結ぶ枝からなる。

木の特徴としては、任意の2点結ぶ経路が一つである。
もっと、「木構造」について調べてみよう。
戻る
一覧へ
次へ
|