从javascript中的平面数组构建树数组

Question

从javascript中的平面数组构建树数组我有一个复杂的json文件，为了以后构建一棵树，我必须用javascript来处理它，使其具有层次结构。json的每个条目都有：id：一个唯一的id，parentId：父节点的id(如果节点是树的根，则为0)级别：树中的深度级别。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         },     ]

Answer 1

如果使用地图查找，有一个有效的解决方案。如果父母总是先于他们的孩子，你可以合并这两个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)，这可能是一个大数据集的问题.