从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

回到顶部