二分木は、各ノードが最大で2つの子（left と right と呼ばれる）を持つ階層構造です。単一のルートを持ち、子を持たないノードは葉です。BST、ヒープ、式木の基礎となります。
構造
text
1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
二分木は、各ノードが最大で2つの子（left と right と呼ばれる）を持つ階層構造です。単一のルートを持ち、子を持たないノードは葉です。BST、ヒープ、式木の基礎となります。
1 depth 0 (root)
/ \
2 3 depth 1
/ \
4 5 depth 2 (leaves: 4,5,3)
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つのバリエーションです。