19　木構造（二分木）

1. 木構造とは

木構造（ツリー）とは、データを階層的に管理するためのデータ構造です。 家系図やフォルダ構造のように、1つの起点から枝分かれしていく形をしています。

2. 木構造の用語

3. 二分木とは

二分木（バイナリツリー）とは、各節点が最大2つの子しか持たない木構造です。 子はそれぞれ「左の子」「右の子」と区別されます。

4. 二分木の節点の構造

二分木の節点は、以下の3つを持ちます。

節点型: Node
    値型:  value      // この節点が持つデータ
    Node型: left      // 左の子（無いときは null）
    Node型: right     // 右の子（無いときは null）
endtype

5. 木の走査（traversal）

木のすべての節点を順番に訪問することを走査といいます。 訪問順序によって3種類があり、いずれも再帰で書けます。

① 前順（行きがけ順 / preorder）

「自分 → 左 → 右」の順に訪問する。

○ preorder(Node型: node)
    if ( node が null と等しい )
        return
    endif
    node.value を出力      // 自分
    preorder(node.left)    // 左
    preorder(node.right)   // 右

上の木の場合、出力は 1 → 2 → 4 → 5 → 3

② 中順（通りがけ順 / inorder）

「左 → 自分 → 右」の順に訪問する。

○ inorder(Node型: node)
    if ( node が null と等しい )
        return
    endif
    inorder(node.left)     // 左
    node.value を出力      // 自分
    inorder(node.right)    // 右

上の木の場合、出力は 4 → 2 → 5 → 1 → 3

③ 後順（帰りがけ順 / postorder）

「左 → 右 → 自分」の順に訪問する。

○ postorder(Node型: node)
    if ( node が null と等しい )
        return
    endif
    postorder(node.left)    // 左
    postorder(node.right)   // 右
    node.value を出力       // 自分

上の木の場合、出力は 4 → 5 → 2 → 3 → 1

6. 二分探索木（BST）

二分探索木（Binary Search Tree）は、以下の決まりを持つ二分木です。

• 左の子（とその子孫すべて）は、親より小さい値
• 右の子（とその子孫すべて）は、親より大きい値

この木で 40 を探す場合：

1. 根 50 と比較 → 40 < 50 なので左へ
2. 30 と比較 → 40 > 30 なので右へ
3. 40 と一致 → 発見！

新しい値の挿入

新しい値を二分探索木に追加するときは、根から比較しながら進み、空いている場所（null）に到達したらそこに置くだけです。

○ insert(Node型: node, 整数型: v)
    if ( node が null と等しい )
        return 新しいノード(value=v, left=null, right=null)
    endif
    if ( v が node.value より小さい )
        node.left ← insert(node.left, v)     // 左の部分木に追加
    elseif ( v が node.value より大きい )
        node.right ← insert(node.right, v)   // 右の部分木に追加
    endif
    return node

例：上の木に 45 を挿入してみる：

1. 根 50 と比較 → 45 < 50 → 左へ移動
2. 30 と比較 → 45 > 30 → 右へ移動
3. 40 と比較 → 45 > 40 → 右へ移動
4. 40 の右は null（空き） → ここに 45 を置く

7. 二分探索木での探索アルゴリズム

○ 論理型: search(Node型: node, 整数型: target)
    if ( node が null と等しい )
        return false                         // 見つからなかった
    endif
    if ( node.value が target と等しい )
        return true                          // 発見
    elseif ( target が node.value より小さい )
        return search(node.left, target)     // 左の部分木を探す
    else
        return search(node.right, target)    // 右の部分木を探す
    endif

8. 計算量

二分探索木がバランスよく形成されているとき、探索の計算量は O(log n) です。

9. 理解度チェック問題

問題19-1

次の木構造の「葉」をすべて挙げなさい。

問題19-2

次の二分木を前順（preorder）で走査したときの出力を選びなさい。

問題19-3

問題19-2と同じ木を中順（inorder）で走査したときの出力を選びなさい。

問題19-4

次の二分探索木に 45 を挿入する場合、どの節点の子になりますか。

問題19-5

二分探索木を中順走査すると、節点の値はどのように出力されますか。