木構造（ツリー）
まず結論
木構造は階層的なデータ表現に使われます。二分木は各ノードが最大2つの子を持ち、二分探索木（BST）は「左の子 ＜ 親 ＜ 右の子」の性質でO(log n)の高速検索を実現します。ファイルシステムや構文解析など至る所で使われます。
木構造の用語
8
根ノード（Root）深さ0
3
深さ1
10
深さ1
1
葉
6
葉
9
葉
14
葉
この木の高さ（height）= 2 ／ ノード数 = 7
重要な用語
・根（Root）: 最上位のノード
・葉（Leaf）: 子を持たないノード
・深さ: 根からの距離
・高さ: 最大の深さ
二分木の性質
各ノードの子ノードが最大2つ。左の子と右の子。
2分探索木・ヒープ・AVL木などは二分木の一種。
二分探索木（BST）
すべてのノードについて「左の子 ＜ 親 ＜ 右の子」が成り立つ二分木。この性質によりO(log n)で探索できます。
BSTでの「8」を探す手順（上の木から「9」を探す場合）
① 根(8)と比較：9 > 8 → 右へ
② 10と比較：9 < 10 → 左へ
③ 9と比較：一致！見つかった
→ 3回の比較で完了。線形探索なら最大7回必要。
① 根(8)と比較：9 > 8 → 右へ
② 10と比較：9 < 10 → 左へ
③ 9と比較：一致！見つかった
→ 3回の比較で完了。線形探索なら最大7回必要。
木の探索順序（3種類）
・前順（Pre-order）: 根→左→右（8,3,1,6,10,9,14）
・中順（In-order）: 左→根→右（1,3,6,8,9,10,14）← 昇順ソートになる！
・後順（Post-order）: 左→右→根（1,6,3,9,14,10,8）
・前順（Pre-order）: 根→左→右（8,3,1,6,10,9,14）
・中順（In-order）: 左→根→右（1,3,6,8,9,10,14）← 昇順ソートになる！
・後順（Post-order）: 左→右→根（1,6,3,9,14,10,8）
🎯 試験での出方
- 「二分探索木の特性」→ 左子 ＜ 親 ＜ 右子
- 「二分木の中順探索（In-order）の結果」→ 昇順に並んだ値
- 木のノード数・高さ・葉の数を問う問題
- 二分探索木への要素挿入後の構造を問う問題
⚠️ よくある間違い
- 「高さ＝ノードの数」→ ✗ 高さは根から最も遠い葉までの辺の数（またはノード数-1）
- 「二分木＝二分探索木」→ ✗ 二分木は子が2つ以下というだけ。BSTはさらに大小関係の制約がある
- 「In-order探索で降順になる」→ ✗ In-orderは昇順（左→根→右なので小さい順）
✍️ 確認クイズ
Q1. 二分探索木（BST）の性質として正しいものはどれか。
✅ 正解は②。二分探索木では全ノードについて「左の子の値 ＜ 親の値 ＜ 右の子の値」が成り立ちます。この性質によりO(log n)の検索が可能です。
Q2. 二分探索木を中順（In-order）で探索すると結果はどうなるか。
✅ 正解は②。BSTの中順探索（左→根→右）は昇順に値を訪問します。これはBSTのソート特性によるものです。
Q3. 木構造において、子ノードを持たないノードを何というか。
✅ 正解は③。子ノードを持たない末端のノードを葉（Leaf）または終端ノードと言います。根（Root）は最上位のノード、枝は中間ノードを指します。
Q4. 二分探索木に値を挿入するとき、値5を上の木（根:8, 左:3[左:1,右:6], 右:10[左:9,右:14]）に挿入した場合の位置はどれか。
✅ 正解は①②。挿入の手順：根8と比較→5<8なので左へ→3と比較→5>3なので右へ→6と比較→5<6なので左へ→空なのでここに挿入。結果、5はノード6の左の子になります。BSTへの挿入はこのように根から比較を繰り返して空き場所を探します。
Q5. 前順（Pre-order）探索の順序として正しいものはどれか。
✅ 正解は③。木の3種類の探索順序：前順（Pre-order）= 根→左→右、中順（In-order）= 左→根→右（BSTで昇順になる）、後順（Post-order）= 左→右→根。この問題の木では前順の結果は8,3,1,6,10,9,14となります。
Sponsor Link