【JavaScript】フラットな配列から階層ツリー構造を構築する方法

JavaScriptで複雑なJSONファイルを処理し、階層構造（ツリー）を持つデータへ変換したい場面はよくあります。例えば、ツリー形式のUIを構築したり、カテゴリの親子関係を表現したりするケースです。本記事では、フラットなJSON配列を親子関係をもつツリー構造へ変換する方法を解説します。

元データの構造

今回扱うJSON配列の各要素は、次のプロパティを持っています。

• id：ノードを一意に識別するID
• parentId：親ノードのID（ツリーのルートの場合は「0」）
• level：ツリー内における階層の深さ

入力データはすでに「整列済み」であるものとします。つまり、ある要素より上には必ずその親ノードまたは兄弟ノードが、下には子ノードまたは兄弟ノードが配置されている順序です。

入力データ

変換前のフラットな配列は以下のとおりです。

const arr = [
    {
        "id": "12",
        "parentId": "0",
        "text": "Man",
        "level": "1",
        "children": null
    },
    {
        "id": "6",
        "parentId": "12",
        "text": "Boy",
        "level": "2",
        "children": null
    },
    {
        "id": "7",
        "parentId": "12",
        "text": "Other",
        "level": "2",
        "children": null
    },
    {
        "id": "9",
        "parentId": "0",
        "text": "Woman",
        "level": "1",
        "children": null
    },
    {
        "id": "11",
        "parentId": "9",
        "text": "Girl",
        "level": "2",
        "children": null
    }
];

期待する出力

変換後は、各ノードの children プロパティに子ノードがネストされた、次のようなツリー構造になります。

const output = [
    {
        "id": "12",
        "parentId": "0",
        "text": "Man",
        "level": "1",
        "children": [
            {
                "id": "6",
                "parentId": "12",
                "text": "Boy",
                "level": "2",
                "children": []
            },
            {
                "id": "7",
                "parentId": "12",
                "text": "Other",
                "level": "2",
                "children": []
            }
        ]
    },
    {
        "id": "9",
        "parentId": "0",
        "text": "Woman",
        "level": "1",
        "children": [
            {
                "id": "11",
                "parentId": "9",
                "text": "Girl",
                "level": "2",
                "children": []
            }
        ]
    }
];

変換処理の実装

ポイントは、各ノードの配列上の位置（インデックス）を id をキーとしたマップに記録しておくことです。これにより parentId から親ノードを即座に参照でき、全体をわずか2回のループで処理できます。計算量は O(n) となるため、大量のデータでも高速に動作します。

1. 1周目のループで、全ノードのインデックスをマップに登録し、children を空配列で初期化する
2. 2周目のループで、parentId が「0」のノードはルートとして結果配列へ追加し、それ以外のノードはマップ経由で親ノードの children に追加する

実際のコードは次のとおりです。

const listToTree = (arr = []) => {
    let map = {}, node, res = [], i;
    // 1周目：インデックスを記録し、children を空配列で初期化
    for (i = 0; i < arr.length; i += 1) {
        map[arr[i].id] = i;
        arr[i].children = [];
    }
    // 2周目：parentId を頼りに親子関係を組み立てる
    for (i = 0; i < arr.length; i += 1) {
        node = arr[i];
        if (node.parentId !== "0") {
            arr[map[node.parentId]].children.push(node);
        } else {
            res.push(node);
        }
    }
    return res;
};
console.log(JSON.stringify(listToTree(arr), undefined, 4));

出力結果

コンソールには次のように出力されます。「Man」と「Woman」がルートノードとなり、それぞれの子ノードが正しくネストされていることが確認できます。

[
    {
        "id": "12",
        "parentId": "0",
        "text": "Man",
        "level": "1",
        "children": [
            {
                "id": "6",
                "parentId": "12",
                "text": "Boy",
                "level": "2",
                "children": []
            },
            {
                "id": "7",
                "parentId": "12",
                "text": "Other",
                "level": "2",
                "children": []
            }
        ]
    },
    {
        "id": "9",
        "parentId": "0",
        "text": "Woman",
        "level": "1",
        "children": [
            {
                "id": "11",
                "parentId": "9",
                "text": "Girl",
                "level": "2",
                "children": []
            }
        ]
    }
]

まとめ

マップによるインデックス管理を活用すれば、フラットなJSON配列でも各ノードを1回ずつ走査するだけでツリー構造へ変換できます。再帰呼び出しを使わないシンプルな実装のため、階層が深いデータでもスタックオーバーフローの心配なく安全に処理できる点も大きなメリットです。メニューや組織図など、階層データを扱うあらゆる場面で応用できるテクニックなので、ぜひ覚えておきましょう。