JavaScriptの木構造における通りがけ順（In-order）走査の解説

通りがけ順走査（In-order Traversal）とは

通りがけ順走査は、木構造の走査方法のひとつで、左部分木 → 根（ルート） → 右部分木 の順にノードを訪問します。ここで重要なのは、すべてのノードがそれ自体ひとつの部分木とみなせるという点です。つまり、各ノードに対して同じルールを再帰的に適用していくことになります。

二分探索木（BST）を通りがけ順で走査すると、キーの値が昇順にソートされた状態で出力されるという特徴があります。これは二分探索木の非常に便利な性質のひとつです。

走査の流れ

まず A から出発し、通りがけ順のルールに従って左部分木の B へ移動します。B に対しても同様に通りがけ順の走査を適用し、この処理をすべてのノードを訪問し終えるまで繰り返します。この木を通りがけ順で走査した結果の出力は以下のようになります。

D → B → E → A → F → C → G

アルゴリズムの考え方

実装するアルゴリズムはシンプルで、次の3ステップで構成されます。

• 左部分木を再帰的に走査する
• ノードのデータを出力する
• 右部分木を再帰的に走査する

クラスへの実装

それでは、クラス内でどのように実装するかを見ていきましょう。利用者にルートノードを直接渡してもらう必要がないよう、クラスの外側にヘルパー関数を用意する設計にします。

inOrder() {
  inOrderHelper(this.root);
}

ヘルパー関数の実装例

function inOrderHelper(root) {
  if (root !== null) {
    inOrderHelper(root.left);
    console.log(root.data);
    inOrderHelper(root.right);
  }
}

動作確認

以下のコードで実際に動作を確認できます。

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
BST.inOrder();

出力結果

3
5
7
10
12
15
50

なぜ昇順に出力されるのか

出力結果を見ると、要素がソートされた順序で表示されていることがわかります。これは、再帰処理によって常に左部分木から先に探索するためです。二分探索木では左側に小さい値が配置されるため、最小の値から順に取得でき、最終的にすべての要素が昇順に並んだ状態で出力されます。この性質を利用すれば、二分探索木をソート済みリストとして扱うことも可能です。