二分木とは何か、また一般的な走査順序は何か？

Question

IT Interview Practice · Accepted Answer

**二分木**は、各**ノード**が最大で**2つの子**（`left` と `right` と呼ばれる）を持つ階層構造です。単一の**ルート**を持ち、子を持たないノードは**葉**です。BST、ヒープ、式木の基礎となります。

## 構造

```text
        1            depth 0 (root)
       / \
      2   3          depth 1
     / \
    4   5            depth 2 (leaves: 4,5,3)
```

## 走査

```python
class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def inorder(n):     # left, node, right -> 4 2 5 1 3
    if n:
        inorder(n.left); print(n.val); inorder(n.right)

def preorder(n):    # node, left, right -> 1 2 4 5 3
    if n:
        print(n.val); preorder(n.left); preorder(n.right)

def postorder(n):   # left, right, node -> 4 5 2 3 1
    if n:
        postorder(n.left); postorder(n.right); print(n.val)
```

**レベルオーダー**（BFS）走査はキューを使用し、深さ順に訪問します。

| 走査 | 順序 | 一般的な用途 |
|---|---|---|
| 中順 | L, N, R | BST の整列出力 |
| 前順 | N, L, R | ツリーのコピー/シリアライズ |
| 後順 | L, R, N | ツリーの削除、式の評価 |
| レベルオーダー | 深さ順 | BFS、ツリー上の最短経路 |

各走査はすべてのノードを1回訪問します → **O(n)** 時間、**O(h)** スタック空間（`h` はツリーの高さ）。

## なぜ重要なのか

二分木は自然に階層データ（ファイルシステム、構文木、判定木）をモデル化し、効率的な探索と整列構造を支えます。

4つの走査をマスターすることは不可欠です — ほとんどのツリーインタビュー問題はそのうちの1つのバリエーションです。

走査	順序	一般的な用途
中順	L, N, R	BST の整列出力
前順	N, L, R	ツリーのコピー/シリアライズ
後順	L, R, N	ツリーの削除、式の評価
レベルオーダー	深さ順	BFS、ツリー上の最短経路

構造

走査

なぜ重要なのか

関連する質問