javascript - 邻接表的树结构

Question

我正在尝试从具有父 ID 的平面数组生成分层树对象。

// `parent` represents an ID and not the nesting level.
var flat = [
    { id: 1, name: "Business", parent: 0 },
    { id: 2, name: "Management", parent: 1 },
    { id: 3, name: "Leadership", parent: 2 },
    { id: 4, name: "Finance", parent: 1 },
    { id: 5, name: "Fiction", parent: 0 },
    { id: 6, name: "Accounting", parent: 1 },
    { id: 7, name: "Project Management", parent: 2  }
];

最终的树对象应该如下所示:

{ 
    id: 1, 
    name: "Business", 
    children: [
        { 
            id: 2, 
            name: "Management", 
            children: [
                { id: 3, name: "Leadership" },
                { id: 7, name: "Project Management" }
            ]
        }
        // [...]
    ]
}
// [...]

您可以在 this fiddle 上看到我目前的工作, 但它只适用于前两个级别。

我考虑过收集孤儿(flat 中的对象在 tree 中还没有父对象)，然后再次遍历它们以查看它们现在是否有父对象。但这可能意味着在树对象上有很多循环，尤其是在多个级别的许多类别中。

我确信有更优雅的解决方案。

Answer 1

看起来无论树的深度如何，您都可以在 2 遍中完成此操作:

var flat = [
    { id: 1, name: "Business", parent: 0 },
    { id: 2, name: "Management", parent: 1 },
    { id: 3, name: "Leadership", parent: 2 },
    { id: 4, name: "Finance", parent: 1 },
    { id: 5, name: "Fiction", parent: 0 },
    { id: 6, name: "Accounting", parent: 1 },
    { id: 7, name: "Project Management", parent: 2  }
];

var nodes = [];
var toplevelNodes = [];
var lookupList = {};

for (var i = 0; i < flat.length; i++) {
    var n = {
        id: flat[i].id,
        name: flat[i].name,
        parent_id: ((flat[i].parent == 0) ? null : flat[i].parent),
        children: []
        };
    lookupList[n.id] = n;
    nodes.push(n);
    if (n.parent_id == null) {
        toplevelNodes.push(n);
    }
}

for (var i = 0; i < nodes.length; i++) {
  var n = nodes[i];
  if (!(n.parent_id == null)) {
      lookupList[n.parent_id].children = lookupList[n.parent_id].children.concat([n]);
  }
}

console.log(toplevelNodes);