全体像
「木構造探索（ツリートラバーサル）」とは、ツリー形式のデータ構造において、すべてのノードを特定のルールに従って一度ずつ訪問することを指します。
リストや配列のような「直線的」なデータ構造とは異なり、ツリーは「階層的」な構造を持ち、一つのノードが複数の子ノードを持つことができます。そのため、ルートや順番など、幾つか異なる探索パターンを定義できます。
木（ツリー）構造を探索するアルゴリズムには大きく2種類があります。BFS（幅優先探索）とDFS（深さ優先探索）です。
BFS（幅優先探索）
BFSはキューを使い、同じ深さのノードをすべて訪問してから次の深さに進みます。
訪問順: A → B → C → D → E → F → G
最短経路を求める問題（迷路など）に適しています。
DFS（深さ優先探索）
DFSはスタック（または再帰）を使い、できる限り深くたどってから戻ります。訪問タイミングで3種類あります。
- 前順（Pre-order）: 自分 → 左 → 右
- 中順（In-order）: 左 → 自分 → 右（二分探索木の昇順出力に使用）
- 後順（Post-order）: 左 → 右 → 自分（ファイルサイズ集計など）
計算量
vはノード数、eはエッジ数、hは木の高さとすると、BFSもDFSも時間計算量はO(V + E)ですが、空間計算量はBFSがO(V)、DFSがO(H)となります。
| アルゴリズム | 時間計算量 | 空間計算量 |
|---|
| BFS | O(V + E) | O(V) |
| DFS | O(V + E) | O(H)（H = 木の高さ） |
インタラクティブデモ
アルゴリズムを選んで「次へ」ボタンを押すと、ノードが訪問される順番を一歩ずつ確認できます。