木構造（二分木）とは？きこうぞう
木構造（二分木）とは、1つの根から枝分かれして節点がつながる階層構造で、閉路を持たないグラフの一種。各節点が最大2個の子を持つものを二分木、左部分木の値が親より小さく右部分木が大きい規則を持つものを二分探索木と呼び、探索・挿入・削除が木の高さに比例する計算量で済む。巡回法は行きがけ・通りがけ・帰りがけの3種。
最終更新：2026-10-06
この語が出る過去問を解く →背景
配列は添字で一発に届く代わりに途中への挿入が重く、連結リストは挿入が軽い代わりに探索が先頭からの走査になる。この二者択一を崩すため、比較のたびに候補を半分に絞れる形へデータを並べたのが探索木で、探索と更新の両方をlog nに寄せるのが狙いである。応用情報では計算量の見積り、巡回順の記述、ヒープの再構成手順として問われる。
具体例
二分探索木では根から比較で左右どちらへ進むかを決めるため、平均で件数の対数に比例する回数で目的の値に届く。データベースの索引に使われるB木・B+木も、1節点に多数の子を持たせて木の高さを抑えた木構造で、ディスクの読み出し回数を減らすための拡張になっている。
試験での引っ掛け
二分探索木は挿入順によって形が偏り、昇順に挿入すると一直線になって探索がO(n)まで劣化する。O(log n)は形が均衡している場合の話で無条件の保証ではない——AVL木や赤黒木は回転でこの偏りを直す仕組みである。通りがけ順（中間順）で巡回すると昇順に並ぶ点も頻出。
関連用語
出た過去問
問題文で直接問われたものと、解説の中で触れられたものが含まれます。
出典：平成29年度 秋期 応用情報技術者試験 午前 問5（IPA）
配列A[1]、A[2]、…、A[n]で、A[1]を根とし、A[i]の左側の子をA[2i]、右側の子をA[2i+1]とみなすことによって、2分木を表現する。このと…
正解：幅優先探索
要点：配列表現の並び順は2分木の幅優先探索と一致する
この配列表現ではA[1]が根、A[2]とA[3]が深さ1、A[4]〜A[7]が深さ2というように、同じ深さのノードが配列上で連続して並ぶ。したがって配列を先頭から順に調べることは、根に近い階層から順に、各階層内は左から右へ辿ることを意味し、幅優先探索に相当する。
出典：平成29年度 秋期 応用情報技術者試験 午前 問46（IPA）
モジュール設計に関する記述のうち、モジュール強度（結束性）が最も強いものはどれか。
正解：ある木構造データを扱う機能をこのデータとともに一つにまとめ、木構造データをモジュールの外から見えないようにした。
要点：モジュール強度は機能的、次いで情報的が強い
モジュール強度は、機能的強度が最も強く、次いで情報的強度が強い。あるデータ構造とそれを操作する機能をひとまとめにし、内部の構造を外部から隠蔽したものは情報的強度に当たり、選択肢の中で最も強い。他の選択肢は論理的・時間的・連絡的といったより弱い強度である。
出典：平成30年度 秋期 応用情報技術者試験 午前 問6（IPA）解説で登場
葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまで…
正解：葉の個数がnならば，葉以外の節点の個数はn-1である。
要点：完全2分木では葉n個に対し内部節点はn−1個になる。
葉以外がすべて2つの子をもち、根から各葉までの深さが等しい木（完全な2分木）では、深さnのとき葉は2^n個、節点の総数は2^(n+1)−1個になる。ここで、葉がn個であれば葉以外（内部節点）は必ずn−1個になる。これは節点総数が2n−1で、そこから葉のn個を引くと得られる関係である。
出典：平成30年度 春期 応用情報技術者試験 午前 問26（IPA）
関係データベースのテーブルにレコードを1件追加したところ、インデックスとして使う、図のB+木のリーフノードCがノードC1とC2に分割された。ノード分割後のB+木…
正解：イ：中間ノードAからB、C1、C2、Dの4つ全てに矢印。リーフノードは B⇔C1⇔C2⇔D の順で相互連結。
要点：B+木は全リーフを親が参照し順序どおり連結する
B+木ではすべてのキーがリーフノードに置かれ、リーフ同士が順次アクセス用のポインタで連結される。リーフが分割されたときは、新しいリーフも親ノードから参照されるようポインタを追加し、リーフ間の連結もキー順を保つよう張り替える必要がある。したがって親AからB・C1・C2・Dの4つすべてへポインタがあり、リーフがB⇔C1⇔C2⇔Dの順で連結された構造が正しい。
出典：令和3年度 春期 応用情報技術者試験 午前 問6（IPA）
配列A[1]，A[2]，…，A[n]で、A[1]を根とし、A[i]の左側の子をA[2i]、右側の子をA[2i+1]とみなすことによって、2分木を表現する。このと…
正解：幅優先探索
要点：ヒープ形式の配列表現の添字順は幅優先の訪問順
この配列表現では、添字の小さい順に根、深さ1の全ノード、深さ2の全ノード…と並ぶ。したがって配列を先頭から順に走査することは、根から始めて同じ深さのノードを左から右へ順に訪問することに等しく、幅優先探索と一致する。深さ優先の3種はいずれも部分木を深く潜ってから戻るため、この並びにはならない。
出典・参考
公式シラバスの1 基礎理論 ＞ 1. データ構造 ＞ (2) データ構造の種類に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。