【JavaScript】階層的なデータ構造の探索（ツリー探索）

【JavaScript】階層的なデータ構造の探索（ツリー探索）

コメント 0件のコメント

はじめに

階層的なデータ構造の探索は、ツリーやグラフのようなデータ構造で情報を検索・取得するための基本的な技法です。JavaScriptでは、ツリー構造を扱う際に、深さ優先探索（DFS）や幅優先探索（BFS）が一般的に使用されます。本稿では、これらの探索方法を解説し、具体的なコード例を通して理解を深めます。

ツリー構造の基本

ツリー構造は、親ノードと子ノードからなる階層的なデータ構造です。ツリーの最上位にあるノードは「ルートノード」と呼ばれ、その下に複数の子ノードが存在することができます。各ノードは他のノードとリンク（親子関係）を持ちます。


const tree = {
    value: 1,
    children: [
        { value: 2, children: [] },
        { 
            value: 3, 
            children: [
                { value: 4, children: [] },
                { value: 5, children: [] }
            ]
        }
    ]
};

上記の例では、ツリーのルートノードは「1」で、子ノードとして「2」と「3」を持っています。ノード「3」にはさらに「4」と「5」という子ノードがあります。

深さ優先探索は、ツリーを探索する際に、まず可能な限り深く子ノードを探索し、行き止まりに達した場合に後戻りして次のノードを探索する方法です。この方法は、再帰的に実装されることが多いです。


function depthFirstSearch(node) {
    console.log(node.value); // ノードを処理
    node.children.forEach(child => depthFirstSearch(child)); // 子ノードを再帰的に探索
}

depthFirstSearch(tree);  // 出力: 1, 2, 3, 4, 5

この例では、深さ優先探索を実行すると、ツリーのノード「1」から順番に「2」「3」「4」「5」が訪問されます。

幅優先探索は、ツリーのレベルごとに順番に探索を行う方法です。つまり、最初にルートノードを訪れ、その後、同じ深さのノードを左から右へと探索します。


function breadthFirstSearch(root) {
    const queue = [root];  // 最初にルートノードをキューに入れる
    while (queue.length > 0) {
        const node = queue.shift();  // キューからノードを取り出す
        console.log(node.value); // ノードを処理
        queue.push(...node.children);  // 子ノードをキューに追加
    }
}

breadthFirstSearch(tree);  // 出力: 1, 2, 3, 4, 5

幅優先探索では、最初にノード「1」を処理した後、次にノード「2」と「3」を処理し、最後に「4」と「5」を処理します。

再帰を使った探索

再帰を使用したツリー探索は、特に深さ優先探索で有効です。再帰的な関数呼び出しを利用して、親ノードから子ノードへと順次探索していきます。


function recursiveTraversal(node) {
    console.log(node.value);  // ノードを処理
    if (node.children.length > 0) {
        node.children.forEach(child => recursiveTraversal(child));  // 子ノードを再帰的に探索
    }
}

recursiveTraversal(tree);  // 出力: 1, 2, 3, 4, 5

再帰関数を使用することで、コードがシンプルで直感的になります。子ノードが存在する限り再帰的に探索を続けます。

実際の例

以下は、実際のアプリケーションで使用されるツリー探索の例です。

ファイルシステムのツリー探索

ファイルシステムのディレクトリ構造もツリー構造です。以下のように、深さ優先探索を使ってディレクトリ内のファイルを探索できます。


const filesystem = {
    name: "root",
    children: [
        { name: "folder1", children: [{ name: "file1.txt", children: [] }] },
        { name: "folder2", children: [{ name: "file2.txt", children: [] }] },
        { name: "file3.txt", children: [] }
    ]
};

function exploreFileSystem(node) {
    console.log(node.name);  // ディレクトリまたはファイル名を表示
    node.children.forEach(child => exploreFileSystem(child));  // 再帰的に探索
}

exploreFileSystem(filesystem);  // 出力: root, folder1, file1.txt, folder2, file2.txt, file3.txt

階層的なメニューの表示

階層的なメニューもツリー構造として表現できます。深さ優先探索を使ってメニュー項目を表示する例を紹介します。


const menu = {
    label: "Home",
    children: [
        { label: "About Us", children: [] },
        { label: "Services", children: [
            { label: "Web Development", children: [] },
            { label: "SEO", children: [] }
        ]},
        { label: "Contact", children: [] }
    ]
};

function displayMenu(node) {
    console.log(node.label);  // メニュー項目を表示
    node.children.forEach(child => displayMenu(child));  // 子メニューを再帰的に表示
}

displayMenu(menu);  // 出力: Home, About Us, Services, Web Development, SEO, Contact

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です