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

Question

我有一个 javascript 对象数组，对象看起来像这样:

itemId
name
parentItemId <== top level items with no parent have null value

我想构建一个图表，其中父项包含子项数组，而那些子项包含子项数组(如果适用)。

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

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 属性，如果节点没有 child ，则该属性为空。我个人认为它比每个节点可能有或可能没有 child 更简单、更一致；您可以遍历 children 而不必担心它是否存在。叶节点将具有 children.length == 0。

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