JavaScriptで親子関係を持つ配列をレベル別にツリー構造へ変換する方法

親子関係を持つ配列をツリー構造へ変換する

同一の配列の中に1対多の親子関係を持つデータを扱う場面は少なくありません。たとえば組織図のようなデータでは、階層が「レベル（level）」によって定義され、各要素の親は必ず自分より1段上のレベルに存在し、parentIdプロパティで参照されます。

本記事では、このようなフラットな配列から多階層のツリー構造（ネストされた配列）を生成する方法を解説します。最上位レベルの要素がメイン（ルート）となり、その子要素はchildrenというサブ配列として格納されます。

入力データの例

入力配列が次のように与えられたとします。

const arr = [
    {
        _id: 100,
        level: 3,
        parentId: null,
    },
    {
        _id: 101,
        level: 2,
        parentId: 100,
    },
    {
        _id: 102,
        level: 2,
        parentId: 100,
    },
    {
        _id: 103,
        level: 2,
        parentId: 100,
    },
    {
        _id: 104,
        level: 1,
        parentId: 101,
    },
    {
        _id: 105,
        level: 1,
        parentId: 102,
    },
    {
        _id: 106,
        level: 1,
        parentId: 101,
    },
    {
        _id: 107,
        level: 1,
        parentId: 103,
    },
    {
        _id: 108,
        level: 1,
        parentId: 102,
    },
    {
        _id: 109,
        level: 1,
        parentId: 103,
    }
];

この入力から得られるべき出力は、次のようなツリー構造です。

100
├── 101
│   ├── 104
│   └── 106
├── 102
│   ├── 105
│   └── 108
└── 103
    ├── 107
    └── 109

実装コード

この変換を行うコードは次のようになります。

// 前述の arr を入力として使用します
const prepareTree = (arr = [], root = null) => {
    let res;
    // プロトタイプを持たない空のマップを生成
    const obj = Object.create(null);
    arr.forEach(el => {
        // 同じIDの仮オブジェクトが既にあれば、その children を引き継ぐ
        el.children = obj[el._id] && obj[el._id].children;
        obj[el._id] = el;
        if (el.parentId === root) {
            // parentId が null の要素がルート
            res = el;
        }
        else {
            // 親がまだ実体化していなければ仮オブジェクトを作る
            obj[el.parentId] = obj[el.parentId] || {};
            obj[el.parentId].children = obj[el.parentId].children || [];
            obj[el.parentId].children.push(el);
        }
    });
    return res;
};

console.log(JSON.stringify(prepareTree(arr), undefined, 4));

アルゴリズムの仕組み

このアプローチのポイントは、以下の通りです。

• Object.create(null)で生成したプレーンなマップに、各要素を_idをキーとして順に登録していきます。
• 要素を処理する際、同じIDがマップに既に存在する場合（＝子要素が先に現れ、親の仮オブジェクトが作られていた場合）は、既存のchildrenをそのまま引き継ぎます。
• parentIdがnullと一致する要素はルートとして、結果変数resに保持されます。
• それ以外の要素は、親IDをキーとするマップのエントリ（存在しなければ新規作成）のchildren配列に追加されます。

すべての子要素は親オブジェクトへの参照を共有しているため、親が配列の後半に登場してもリンクは自動的に維持されます。その結果、配列を一度だけ走査するだけで済み、計算量はO(n)ときわめて効率的です。

出力結果

コンソールに出力されるJSONは次のようになります。

{
    "_id": 100,
    "level": 3,
    "parentId": null,
    "children": [
        {
            "_id": 101,
            "level": 2,
            "parentId": 100,
            "children": [
                {
                    "_id": 104,
                    "level": 1,
                    "parentId": 101
                },
                {
                    "_id": 106,
                    "level": 1,
                    "parentId": 101
                }
            ]
        },
        {
            "_id": 102,
            "level": 2,
            "parentId": 100,
            "children": [
                {
                    "_id": 105,
                    "level": 1,
                    "parentId": 102
                },
                {
                    "_id": 108,
                    "level": 1,
                    "parentId": 102
                }
            ]
        },
        {
            "_id": 103,
            "level": 2,
            "parentId": 100,
            "children": [
                {
                    "_id": 107,
                    "level": 1,
                    "parentId": 103
                },
                {
                    "_id": 109,
                    "level": 1,
                    "parentId": 103
                }
            ]
        }
    ]
}

この手法は、カテゴリ一覧、コメントスレッド、組織図など、データベースから取得したフラットな行データをUI向けのネスト構造へ変換したい場面で幅広く活用できます。