JavaScriptにおける木構造の走査（ツリートラバーサル）入門

木構造の走査（ツリートラバーサル）とは

木構造の走査（ツリートラバーサル）とは、ツリー（木）データ構造に含まれる各ノードを、正確に一度ずつ訪問する処理のことを指します。ツリーは階層的なデータ構造であるため、配列のような線形構造とは異なり、どの順序でノードを辿るかが重要な設計要素となります。この走査順序によって、トラバーサルはいくつかの種類に分類されます。

主な走査方法の種類

木構造の走査は、大きく「深さ優先探索（DFS）」と「幅優先探索（BFS）」の2つに分けられます。

深さ優先探索（DFS）

深さ優先探索は、あるノードから出発して子孫方向へできる限り深く進み、行き止まりに達したら戻りながら次の経路を探索する方式です。さらに、ノードを訪問するタイミングによって以下の3種類に分類されます。

• 先行順（前順・Preorder）： 親ノード → 左の子 → 右の子 の順で訪問します。木構造の複製を作成する際などに利用されます。
• 中間順（中順・Inorder）： 左の子 → 親ノード → 右の子 の順で訪問します。二分探索木において、昇順にソートされたデータを取得できます。
• 後行順（Postorder）： 左の子 → 右の子 → 親ノード の順で訪問します。子ノードを先に処理してから親を削除したい場合などに適しています。

幅優先探索（BFS）

幅優先探索（レベル順走査とも呼ばれます）は、根（ルート）に近いノードから順に、同じ深さのノードを横方向へ訪問していく方式です。通常はキュー（Queue）というデータ構造を使用して実装されます。木の高さや最短距離を求めたい場合に有効です。

まとめ

JavaScriptで木構造を扱う際には、目的に応じて適切な走査方法を選択することが重要です。再帰関数を使えば深さ優先探索を簡潔に実装でき、キューを使えば幅優先探索を実装できます。それぞれの特徴を理解し、用途に合わせて使い分けましょう。