1.木構造とは

木構造は、データ間の関係を階層的に表現します。
過去問(H16春FE午前問43)では、木構造に関して「ア 階層の上位から下位に節点をたどることによって,データを取り出すことができる構造である。」と述べられています。
tree
階層の○の部分ですが、最上位が「根」、最下位が「葉」、その間を「節」と呼びます。また、根や葉などを接続する線を「枝」と呼びます。

(1)2分木

すべての節が二つ以内の子(節や葉)をもつもの

(2)完全2分木

2分木の中で、「すべての葉が同じ深さであり,かつ,葉以外のすべての節点が二つの子をもつ(H19春SW午前問9)」ものである。別の過去問では、「根からどの葉に向かって木をたどっても,途中で通るノートの数が同じである完全2分木(H18秋SW午後Ⅰ)」という表現もされている。

(3)B木

枝が2つなのが2分木でしたが、枝が2つより多い場合を多分木と言います。
多分木の中で、葉までの階層が全て同じなどの特徴を持つものをB木と言います。
aaa

2.木構造の過去問を解いてみよう

(1)H29秋AP午前

問6 ノート1~5をもつグラフを隣接行列で表したもののうち,木となるものはどれか。ここで,隣接行列のi行j列目の成分は,ノートiとノートjを結ぶエッジがある場合は1,ない場合は0とする。
H29a-問6






【正解】イ

(2)H25秋AP午前

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

ア 枝の個数がnならば,節点の個数もnである。
イ 木の深さがnならば,葉の個数は2n-1である。
ウ 節点の個数がnならば,深さはlog2nである。
エ 葉の個数がnならば,葉以外の節点の個数はn-1である。






【正解】エ