从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
}
}
]
} 问题来源于stack overflow
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
-
如果使用地图查找，则有一个有效的解决方案。如果父母总是先于孩子，则可以合并两个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），这对于大数据集可能是个问题。
2020-02-08 10:14:11赞同 展开评论