在javascript中从平面数组构建树形数组
在javascript中从平面数组构建树形数组
提问于 2013-08-02 21:17:58
我有一个复杂的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
}
}
]
}回答 26
Stack Overflow用户
回答已采纳
发布于 2013-08-02 21:25:22
如果您使用地图查找，则有一个有效的解决方案。如果父母总是先于他们的孩子，你可以合并这两个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",
"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
}
];
console.log(list_to_tree(entries));
如果你对复杂性理论感兴趣，这个解决方案就是Θ(n (N))。递归过滤器的解决方案是Θ(n^2)，这对于大型数据集来说可能是一个问题。
Stack Overflow用户
发布于 2014-02-27 23:04:59
正如@Sander所提到的，@Halcyon`s answer假设一个预先排序的数组，下面的不是。(但是，它假定您已经加载了underscore.js -尽管它可以用普通的javascript编写)：
代码
// Example usage
var arr = [
{'id':1 ,'parentid' : 0},
{'id':2 ,'parentid' : 1},
{'id':3 ,'parentid' : 1},
{'id':4 ,'parentid' : 2},
{'id':5 ,'parentid' : 0},
{'id':6 ,'parentid' : 0},
{'id':7 ,'parentid' : 4}
];
unflatten = function( array, parent, tree ){
tree = typeof tree !== 'undefined' ? tree : [];
parent = typeof parent !== 'undefined' ? parent : { id: 0 };
var children = _.filter( array, function(child){ return child.parentid == parent.id; });
if( !_.isEmpty( children ) ){
if( parent.id == 0 ){
tree = children;
}else{
parent['children'] = children
}
_.each( children, function( child ){ unflatten( array, child ) } );
}
return tree;
}
tree = unflatten( arr );
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore-min.js"></script>
要求
它假设属性' ID‘和'parentid’分别表示ID和父ID。必须存在父ID为0的元素，否则将返回一个空数组。孤立的元素及其后代都“丢失”了
Stack Overflow用户
发布于 2019-03-19 20:50:06
使用这种ES6方法。作品如魅力
// Data Set
// One top level comment
const comments = [{
id: 1,
parent_id: null
}, {
id: 2,
parent_id: 1
}, {
id: 3,
parent_id: 1
}, {
id: 4,
parent_id: 2
}, {
id: 5,
parent_id: 4
}];
const nest = (items, id = null, link = 'parent_id') =>
items
.filter(item => item[link] === id)
.map(item => ({ ...item, children: nest(items, item.id) }));
console.log(
nest(comments)
)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18017869
复制相关文章
相似问题
腾讯云开发者
