JavaScriptで学ぶ木構造の先行順走査（Pre-order Traversal）の基本と実装

先行順走査（Pre-order Traversal）は、二分木を巡回する代表的な手法のひとつです。この走査方法では、まずルートノードを訪問し、次に左部分木、最後に右部分木の順で処理を行います。

先行順走査の流れ

具体的な動きを見てみましょう。まず A から開始し、先行順走査に従って最初に A 自身を訪問します。その後、左部分木である B へ移動します。B も同様に先行順で走査され、この処理はすべてのノードを訪問するまで繰り返されます。

この木に対する先行順走査の結果は以下のようになります。

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

アルゴリズムの手順

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

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

クラスへの実装

それでは、このアルゴリズムをクラス内にどのように実装するか見ていきましょう。

preOrder() {
    preOrderHelper(this.root);
}

ヘルパー関数

実際の走査処理は、再帰呼び出しを行うヘルパー関数が担います。

例

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

この関数では、ノードが存在する場合（null でない場合）に、まずそのデータを表示し、続いて左側・右側の子ノードへ再帰的に処理を進めています。

動作確認

実際にコードを実行して動作を確認してみましょう。

例

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.preOrder();

出力結果

上記のコードを実行すると、以下の出力が得られます。

10
5
3
7
15
12
50

ルートの 10 が最初に出力され、その後左部分木（5、3、7）、最後に右部分木（15、12、50）の順に訪問されていることがわかります。これが先行順走査の「根 → 左 → 右」という基本原則です。