木構造・二分木とは？

木構造・二分木の意味

要素（ノード）同士を親子関係でつなぎ、階層的に表現するデータ構造。二分木は各ノードが持つ子ノードを最大2つに限定した木構造で、特に左の子が親より小さく右の子が親より大きくなるよう並べたものを二分探索木という。

木構造・二分木の具体例

ファイルシステムのディレクトリ構造は木構造の典型例。二分探索木では、探索したい値と各ノードを比較しながら左右どちらかへ降りていくことで、平均O(log n)で目的のノードを見つけられる。

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

木の巡回方法には行きがけ順（先行順）・通りがけ順（中間順）・帰りがけ順（後行順）の3種類があり、たどる順序を取り違えやすい。

木構造・二分木と関連する用語

• グラフ理論
• クイックソート・マージソート・ヒープソート

木構造・二分木が出た過去問

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

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

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

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

  出典：平成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）