二分木の走査とは？
二分木の走査(Binary Tree Traversal)は、木の全ノードを決まった順序でちょうど一度ずつ訪れることです。代表的に深さ優先系の前順・中順・後順と、幅優先系のレベル順があります。
核心の一行: 「3つの深さ走査の違いは、いつルートを訪れるかだけ」。 左の子は常に右より先で、ルートの位置だけが前・中・後に変わります。
3つの深さ走査(DFS系)
| 走査 | 順序 | 活用 |
|---|---|---|
| 前順(Preorder) | ルート → 左 → 右 | 木の複製、式の前置記法 |
| 中順(Inorder) | 左 → ルート → 右 | BSTで昇順出力 |
| 後順(Postorder) | 左 → 右 → ルート | 木の削除、後置記法の計算 |
名前の「前/中/後」は子に対していつルートを訪れるかを指します。
中順走査とBST
二分探索木(BST)は「左 < ルート < 右」の規則を守ります。だから中順(左 → ルート → 右)で訪れると値がちょうど昇順で出ます。BSTでの整列出力やk番目の値を探すときにこの性質を使います。
動作原理
ステップ1. 現在のノードが空(null)なら、そのまま戻ります(基底ケース)。
ステップ2. 再帰で3つの動作を行います — 左の子を走査、現在のノードを訪問、右の子を走査。
ステップ3. この3動作の順序を変えるだけで前順・中順・後順になります。訪問を先に置けば前順、中間なら中順、後なら後順。
レベル順は別物です — キューを使い上から下へ、同じ層は左から右へ訪れます(BFS)。
AlgoNoteの可視化は、同じ木を走査方式ごとにどの順でノードを訪れるかをステップごとに示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(n) |
| 空間 | O(h) ~ O(n) |
ノードを一度ずつ見るのでO(n)、再帰空間は木の高さh分です(偏った木ならO(n))。
例で追ってみる
ルート2、左1、右3の木:
- •前順: 2, 1, 3
- •中順: 1, 2, 3 ← 昇順(BST)
- •後順: 1, 3, 2
- •レベル: 2, 1, 3
よくあるミス
- •順序の混同: 唯一の違いがルートの位置だと覚えれば混乱しません。
- •中順=整列を忘れる: BSTで整列出力が必要なら、別途整列せず中順走査を使いましょう。
- •空ノードの処理: nullチェックを抜くと再帰が破綻します。
AlgoNoteで直接確認しましょう
同じ木で前順・中順・後順・レベル走査がそれぞれどの順でノードを訪れるかをAlgoNoteでステップごとに確認できます。