在javascript中从平面对象数组构建对象图

Question

我有一个 javascript 对象数组，其中的对象如下所示：

itemId
名称
parentItemId <== 没有父项的顶级项目具有空值

我想构建一个图形，其中父项包含子项数组，如果适用，这些子项具有子项数组。

什么是解决这个问题的好方法？

Answer 1

function objectGraph(items)
{
    var items_by_id = {};
    var roots = [];
    var i;

    // Build an id->object mapping, so we don't have to go hunting for parents
    for (i = 0; i < items.length; ++i) {
        items_by_id[items[i].itemId] = items[i];
        items[i].children = [];
    }

    for (i = 0; i < items.length; ++i) {
        var parentId = items[i].parentItemId;
        // If parentId is null, this is a root; otherwise, it's parentId's kid
        var nodes = (parentId === null) ? roots : items_by_id[parentId].children;
        nodes.push(items[i]);
    }
    return roots;
}

请注意，此代码为每个节点提供了一个children属性，如果节点没有孩子，则该属性为空。我个人觉得它比每个节点可能——也可能——没有孩子更简单、更一致；你可以循环而children不用担心它是否存在。叶节点将具有children.length == 0.

如果你能保证你只有一个根，你可以return roots[0];不返回数组。