来自邻接表的树结构 [英] Tree Structure from Adjacency List
问题描述
我正在尝试从具有父 ID 的平面数组生成分层树对象.
I am trying to generate a hierarchical tree object from a flat array with parent IDs.
// `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 }
];
最终的树对象应该如下所示:
The final tree object should look as follows:
{
id: 1,
name: "Business",
children: [
{
id: 2,
name: "Management",
children: [
{ id: 3, name: "Leadership" },
{ id: 7, name: "Project Management" }
]
}
// [...]
]
}
// [...]
你可以在这个小提琴上看到我目前的工作,但它只适用于前两个级别.
You can see my current work on this fiddle, but it only works on the first two levels.
我想收集孤儿(来自 flat
的对象,而 tree
中没有父对象),然后再次循环遍历它们,看看它们现在是否有父对象.但这可能意味着在树对象上有许多循环,尤其是在多个级别上有许多类别.
I thought about collecting the orphans (objects from flat
without a parent in tree
yet) and then looping over them again to see if they now have a parent. But that could mean many loops over the tree object, especially with many categories over multiple levels.
我相信有更优雅的解决方案.
I'm sure there is a more elegant solution.
推荐答案
看起来无论树的深度如何,您都可以通过 2 次完成此操作:
Looks like you can do this in 2 passes no matter the tree depth:
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);
这篇关于来自邻接表的树结构的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!