从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&nbsp;list_to_tree(list)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;map&nbsp;=&nbsp;{},&nbsp;node,&nbsp;roots&nbsp;=&nbsp;[],&nbsp;i; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;list.length;&nbsp;i&nbsp;+=&nbsp;1)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;map[list[i].id]&nbsp;=&nbsp;i;&nbsp;//&nbsp;initialize&nbsp;the&nbsp;map &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list[i].children&nbsp;=&nbsp;[];&nbsp;//&nbsp;initialize&nbsp;the&nbsp;children &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;list.length;&nbsp;i&nbsp;+=&nbsp;1)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node&nbsp;=&nbsp;list[i]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(node.parentId&nbsp;!==&nbsp;"0")&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;if&nbsp;you&nbsp;have&nbsp;dangling&nbsp;branches&nbsp;check&nbsp;that&nbsp;map[node.parentId]&nbsp;exists &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list[map[node.parentId]].children.push(node); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;roots.push(node); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;roots;}var&nbsp;entries&nbsp;=&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"id":&nbsp;"12", &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"parentId":&nbsp;"0", &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"text":&nbsp;"Man", &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"level":&nbsp;"1" &nbsp;&nbsp;&nbsp;&nbsp;},&nbsp;{&nbsp;/*...*/&nbsp;}];console.log(list_to_tree(entries));如果您对复杂性理论感兴趣，这个解决方案是Θ(n log(N)。递归过滤解决方案是Θ(n^2)，这可能是一个大数据集的问题.