ENGINEER_GUIDANCE: 木の走査 (Tree Traversal)
ツリー構造のすべてのノードを漏れなく1回ずつ訪問するアルゴリズムです。「深さ優先探索(DFS)」と「幅優先探索(BFS)」に大別されます。
1. Preorder (行きがけ順 / DFS)
自分 → 左の子 → 右の子
の順に訪問します。
ルートノードから深く潜っていく際に、初めてそのノードを訪れたタイミングで処理を行います。ツリーのコピー作成などによく使われます。
2. Inorder (通りがけ順 / DFS)
左の子 → 自分 → 右の子
の順に訪問します。
二分探索木(BST)でこの走査を行うと、値が小さい順(昇順)にソートされて出力されるという重要な特性があります。
3. Postorder (帰りがけ順 / DFS)
左の子 → 右の子 → 自分
の順に訪問します。
子ノードの処理がすべて終わってから自分自身を処理します。ツリーの削除(メモリ解放)や、子ノードの計算結果を使って親の値を決める処理(数式の構文木など)で使われます。
4. BFS (幅優先探索 / Level-order)
ルートから順に同じ階層(レベル)のノードを左から右へ水平に走査します。
最短経路の探索などに利用され、実装には通常「キュー(Queue)」を用います。