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

Question

我有一个复杂的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
            }
        }

    ]
}

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），这对于大数据集可能是个问题。