行きがけ順走査 — ルート、左、右
行きがけ順（NLR）木走査を学びます。部分木の前にルートを訪問します。アルゴリズム、木のシリアライゼーションでの使用法、通りがけ順走査との違いを理解します。
Traversal
詳細な説明
行きがけ順走査（NLR）
行きがけ順走査は ノード、左部分木、右部分木 の順序でノードを訪問します。ルートは常に出力の最初の要素であり、行きがけ順が木のシリアライゼーションと再構築に有用な理由です。
再帰的実装
PREORDER(node):
if node is NULL: return
visit(node) // まずルートを処理
PREORDER(node.left)
PREORDER(node.right)
例
4
/ \
2 6
/ \ / \
1 3 5 7
行きがけ順結果: [4, 2, 1, 3, 6, 5, 7]
ルート（4）が最初に現れ、次に左部分木全体 [2, 1, 3]、次に右部分木全体 [6, 5, 7] が続きます。
木のシリアライゼーションとデシリアライゼーション
行きがけ順走査は BST を一意に表現できます。最初の要素が常にルートであり、ルートより大きい値がどこから始まるかを見つけることで左右の分割を判断できるためです。この性質は以下に使用されます：
- 木の文字列やファイルへのシリアライゼーション
- ネットワーク上での木構造の送信
- 元に戻す/やり直し機能のための木のスナップショット保存
DFS との関係
行きがけ順走査は本質的に木に対する**深さ優先探索（DFS）**です。左の枝に沿ってできるだけ深く探索してからバックトラックします。これが木に対する DFS と行きがけ順走査が左優先で同じ訪問パターンを生成する理由です。
時間・空間計算量
- 時間: O(n) — すべてのノードを正確に1回訪問
- 空間: O(h) — 再帰の深さは木の高さに等しい
ユースケース
行きがけ順走査は木のコピー作成（ルートをクローンし、左右を再帰的にクローン）、ストレージや送信用の木構造のシリアライゼーション、式木からの前置記法の生成に不可欠です。コンパイラは抽象構文木から前置記法を生成するために行きがけ順走査を使用します。