テクノロジ系出題頻度 3/3
二分木
にぶんぎ
定義
各ノードが最大2つの子（左右）を持つ木構造。階層的データの基本表現。
詳細解説
各ノードが左右最大2子を持つ木。完全二分木、全二分木、平衡二分木等の派生がある。走査方法には先行順（pre-order）、中順（in-order）、後行順（post-order）、レベル順（BFS）があり、再帰またはスタック/キューで実装される。ノード数nの木の高さは平衡なら O(log n)、偏ると O(n) になり、探索性能に直結する。二分探索木、ヒープ、AVL木、赤黒木、B木等の基盤構造。
「二分木」が出る問題に挑戦
読んだ内容は“思い出す”ほど記憶に残ります。解答・解説つき・基本無料で確認できます。
完全二分木において、節点数がnのときの木の高さのオーダとして、正しいものはどれか。
二分探索木において、最も小さい要素を取り出すための走査方向として、正しいものはどれか。
二分探索木に関する記述として正しいものはどれか。
関連用語
よくある質問
Q. 二分木とは何ですか？
A. 各ノードが最大2つの子（左右）を持つ木構造。階層的データの基本表現。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。