基本情報技術者試験 練習問題 13：木構造と二分木

木構造はコンピュータサイエンスにおいて重要な非線形データ構造です。

木構造の基本的性質：
- サイクル（閉路）が存在しない（「森」と異なる）
- 1つの根ノード（Root）が存在
- 各ノードは親ノードをただ1つ持つ（根を除く）
- ノードとノードの関係は「親→子」の階層構造

二分木（Binary Tree）※本問の正解：
各ノードが最大2つの子ノードを持つ木構造です。左部分木と右部分木に分かれます。

完全二分木（Complete Binary Tree）：
- レベルkまですべてのノードが埋まっており、レベルk+1は左から順に埋まっている構造。
- 葉以外のすべてのノードが2つの子を持つわけではありません。

二分探索木（Binary Search Tree）：
- 親ノードより小さい値は「左部分木」に配置
- 親ノードより大きい値は「右部分木」に配置
- これにより検索時間がO(log n)で高速化される（ただしバランスが必要）

根ノード：
ただ1つ存在し、すべての他のノードはこの根から到達可能です。複数の根は存在しません。