木構造とは？

木構造の意味

節（ノード）と枝（エッジ）で階層関係を表すデータ構造。最上位の節を根、子を持たない節を葉といい、閉路を持たない。ファイルシステムや組織図、構文解析木などの表現に使われる。節の数nに対し枝の数はn-1になる点がFEで問われる。

木構造の具体例

根から葉までの枝の本数を深さ（レベル）と呼び、木全体の最大深さを高さという。1つの節が持つ子の数を次数といい、次数が最大2の木を二分木と呼ぶ。7個の節を持つ木なら枝は必ず6本になる。

木構造は試験でどう引っ掛けられる？

「閉路がある」ものは木ではなくグラフ。また根は1つだけで、各節の親は高々1つ（根だけが親を持たない）。深さの数え方が「根を0とするか1とするか」で答えがずれるため、問題文の定義を必ず確認する。

木構造と関連する用語

• 二分木
• グラフ
• 木の走査

木構造が出た過去問

• 再帰呼出しの説明はどれか。

  正解：関数の中で自分自身を用いた処理を行うこと

  要点：再帰呼出しは関数が自分自身を呼ぶこと。終了条件が必須

  再帰呼出しとは、ある関数の処理の中でその関数自身を呼び出すことをいう。階乗やハノイの塔、木構造の探索のように、同じ形のより小さい問題に帰着できる処理を簡潔に書ける。呼出しごとにスタックへ戻り番地と局所変数が積まれるため、終了条件を必ず用意する必要がある。

  出典：平成29年度 秋期 基本情報技術者試験 午前 問6（IPA）

• 図の木構造は2分探索木である。a〜gの値の大小関係として，適切なものはどれか。ここで，a〜gの値は重複しないものとする。

  正解：d＜b＜e＜a＜f＜c＜g

  要点：2分探索木は通りがけ順にたどると値が昇順に並ぶ

  2分探索木は、ある節点の左部分木には自分より小さい値、右部分木には自分より大きい値だけが入るという性質をもつ。したがって節点を通りがけ順（左・自分・右）にたどると値が昇順に並ぶ。この木を通りがけ順にたどるとd、b、e、a、f、c、gの順になり、これがそのまま大小関係になる。

  出典：令和7年度 （公開問題） 基本情報技術者試験 kamokuA 問3（IPA）

• 次の記述中の a と b に入れる正しい答えの組合せを、解答群の中から選べ。 三目並べにおいて自分が勝利する可能性が最も高い手を決定する。次の手順で、ゲームの状…

  正解：a: 0, b: －10

  要点：相手の手番の節は子の評価値の最小値を取る

  手順(3)より、相手の手番の節は子の評価値の最小値を取ります。Aが指す節の子は、それぞれ引分け0と自分の勝ち10なので、最小値は0です。Bが指す節の子は、自分の負け－10と引分け0なので、最小値は－10になります。相手は自分にとって最も不利な手を選ぶ、という前提が最小値を取る理由です。

  出典：令和4年度 s 基本情報技術者試験 kamokuB 問15（IPA）