JavaScriptでフラットなJSON配列からツリー構造を構築する方法

JavaScript開発では、ドット区切りの階層コードを持つフラットな配列を、親子関係を表現したネストされたツリー構造へ変換したいケースがよくあります。カテゴリ一覧や組織図、メニュー構成などのデータを扱う際に役立つ処理です。

問題の概要

ここでは、次のような配列を例に考えてみましょう。各オブジェクトは「code」（階層を表すドット区切りコード）と「name」をプロパティとして持っています。

const arr = [{
    "code": "2",
    "name": "PENDING"
},
{
    "code": "2.2",
    "name": "PENDING CHILDREN"
},
{
    "code": "2.2.01.01",
    "name": "PENDING CHILDREN CHILDREN"
},
{
    "code": "2.2.01.02",
    "name": "PENDING CHILDREN CHILDREN02"
},
{
    "code": "1",
    "name": "ACTIVE"
},
{
    "code": "1.1",
    "name": "ACTIVE CHILDREN"
},
{
    "code": "1.1.01",
    "name": "ACTIVE CHILDREN CHILDREN"
}];

この配列では、「2」がルート要素であり、「2.2」はその子要素、「2.2.01.01」はさらにその下の階層にある要素を意味しています。このような配列を受け取り、code の階層構造に基づいてツリーを組み立てる関数を実装します。各ノードには、子要素を格納するための「children」プロパティが付与されます。

期待される出力は次のとおりです。

const output = [{
    "code": "2",
    "name": "PENDING",
    "children": [{
        "code": "2.2",
        "name": "PENDING CHILDREN",
        "children": [{
            "code": "2.2.01.01",
            "name": "PENDING CHILDREN CHILDREN"
        },
        {
            "code": "2.2.01.02",
            "name": "PENDING CHILDREN CHILDREN02"
        }]
    }]
},
{
    "code": "1",
    "name": "ACTIVE",
    "children": [{
        "code": "1.1",
        "name": "ACTIVE CHILDREN",
        "children": [{
            "code": "1.1.01",
            "name": "ACTIVE CHILDREN CHILDREN"
        }]
    }]
}];

実装例

実際のコードは次のようになります。

const arr = [{
    "code": "2",
    "name": "PENDING"
},
{
    "code": "2.2",
    "name": "PENDING CHILDREN"
},
{
    "code": "2.2.01.01",
    "name": "PENDING CHILDREN CHILDREN"
},
{
    "code": "2.2.01.02",
    "name": "PENDING CHILDREN CHILDREN02"
},
{
    "code": "1",
    "name": "ACTIVE"
},
{
    "code": "1.1",
    "name": "ACTIVE CHILDREN"
},
{
    "code": "1.1.01",
    "name": "ACTIVE CHILDREN CHILDREN"
}];
const transformToTree = (arr, root = '') => {
    let map = {}, last = [root], level = 0;
    map[root] = {};
    arr.forEach(el => {
        let parent = root;
        while (level && last[level].length >= el.code.length) {
            level--;
        };
        parent = last[level];
        level++;
        last.length = level;
        last.push(el.code);
        map[el.code] = el;
        map[parent].children = map[parent].children || [];
        map[parent].children.push(el);
    });
    return map[root].children;
};
console.log(JSON.stringify(transformToTree(arr), undefined, 4));

コードの仕組み

この実装のポイントは以下の通りです。

• map: 各ノードへの参照を code をキーとして管理し、親ノードへのアクセスを高速化します。
• last: 現在走査中の階層パス（祖先ノードのコード一覧）をスタックのように保持します。
• level: 新しい要素のコード長と比較しながら階層を遡り、正しい親ノードを見つけます。

このアルゴリズムは配列を一度だけ走査すればよいため、計算量は O(n) となり、大規模なデータセットでも効率的に動作します。

出力結果

コンソールに出力すると、次のようなツリー構造が得られます。

[
    {
        "code": "2",
        "name": "PENDING",
        "children": [
            {
                "code": "2.2",
                "name": "PENDING CHILDREN",
                "children": [
                    {
                        "code": "2.2.01.01",
                        "name": "PENDING CHILDREN CHILDREN"
                    },
                    {
                        "code": "2.2.01.02",
                        "name": "PENDING CHILDREN CHILDREN02"
                    }
                ]
            }
        ]
    },
    {
        "code": "1",
        "name": "ACTIVE",
        "children": [
            {
                "code": "1.1",
                "name": "ACTIVE CHILDREN",
                "children": [
                    {
                        "code": "1.1.01",
                        "name": "ACTIVE CHILDREN CHILDREN"
                    }
                ]
            }
        ]
    }
]