从JavaScript中的平面数组构建树数组
我有一个复杂的json文件,必须使用javascript处理才能使其具有层次结构,以便稍后构建树。json的每个条目都具有:id:唯一ID,parentId:父节点的id(如果节点是树的根,则为0)level:树中的深度级别
json数据已被“排序”。我的意思是,条目上方将具有父节点或兄弟节点,而其下将具有子节点或兄弟节点。
输入:
{ "People": [
{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1",
"children": null
},
{
"id": "6",
"parentId": "12",
"text": "Boy",
"level": "2",
"children": null
},
{
"id": "7",
"parentId": "12",
"text": "Other",
"level": "2",
"children": null
},
{
"id": "9",
"parentId": "0",
"text": "Woman",
"level": "1",
"children": null
},
{
"id": "11",
"parentId": "9",
"text": "Girl",
"level": "2",
"children": null
}
],
"Animals": [
{
"id": "5",
"parentId": "0",
"text": "Dog",
"level": "1",
"children": null
},
{
"id": "8",
"parentId": "5",
"text": "Puppy",
"level": "2",
"children": null
},
{
"id": "10",
"parentId": "13",
"text": "Cat",
"level": "1",
"children": null
},
{
"id": "14",
"parentId": "13",
"text": "Kitten",
"level": "2",
"children": null
},
]
}
预期产量:
{ "People": [
{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1",
"children": [
{
"id": "6",
"parentId": "12",
"text": "Boy",
"level": "2",
"children": null
},
{
"id": "7",
"parentId": "12",
"text": "Other",
"level": "2",
"children": null
}
]
},
{
"id": "9",
"parentId": "0",
"text": "Woman",
"level": "1",
"children":
{
"id": "11",
"parentId": "9",
"text": "Girl",
"level": "2",
"children": null
}
}
],
"Animals": [
{
"id": "5",
"parentId": "0",
"text": "Dog",
"level": "1",
"children":
{
"id": "8",
"parentId": "5",
"text": "Puppy",
"level": "2",
"children": null
}
},
{
"id": "10",
"parentId": "13",
"text": "Cat",
"level": "1",
"children":
{
"id": "14",
"parentId": "13",
"text": "Kitten",
"level": "2",
"children": null
}
}
]
}
回答:
如果使用地图查找,则有一个有效的解决方案。如果父母总是先于孩子,则可以合并两个for循环。它支持多个根。它在悬垂的分支上给出错误,但可以修改以忽略它们。它不需要第三方库。据我所知,这是最快的解决方案。
function list_to_tree(list) { var map = {}, node, roots = [], i;
for (i = 0; i < list.length; i += 1) {
map[list[i].id] = i; // initialize the map
list[i].children = []; // initialize the children
}
for (i = 0; i < list.length; i += 1) {
node = list[i];
if (node.parentId !== "0") {
// if you have dangling branches check that map[node.parentId] exists
list[map[node.parentId]].children.push(node);
} else {
roots.push(node);
}
}
return roots;
}
var entries = [
{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1"
}, { /*...*/ }
];
console.log(list_to_tree(entries));
如果您对复杂性理论感兴趣,则此解为Θ(n log(n))。递归滤波器的解决方案是Θ(n ^ 2),这对于大数据集可能是个问题。
以上是 从JavaScript中的平面数组构建树数组 的全部内容, 来源链接: utcz.com/qa/398022.html