In daily development work, we often encounter the need to transform linear data into trees, today to share with you a simple transformation algorithm.

The data structure

Here is the data before our conversion:

[{"id":1."parent_id":0."name":"Sichuan Province"
    },
    {
        "id":2."parent_id":0."name":"Guangdong Province"
    },
    {
        "id":3."parent_id":0."name":Jiangxi Province
    },
    {
        "id":5."parent_id":1."name":"Chengdu city"
    },
    {
        "id":6."parent_id":5."name":Jinjiang District
    },
    {
        "id":7."parent_id":6."name":Nine Eye Bridge
    },
    {
        "id":8."parent_id":6."name":LAN Kwai Fong
    },
    {
        "id":9."parent_id":2."name":"Dongguan"
    },
    {
        "id":10."parent_id":9."name":"Chang 'an Town"
    },
    {
        "id":11."parent_id":3."name":"Nanchang city"}]Copy the code

The result of our conversion is:

[{"id":1."parent_id":0."name":"Sichuan Province"."children":[
            {
                "id":5."parent_id":1."name":"Chengdu city"."children":[
                    {
                        "id":6."parent_id":5."name":Jinjiang District."children":[
                            {
                                "id":7."parent_id":6."name":Nine Eye Bridge
                            },
                            {
                                "id":8."parent_id":6."name":LAN Kwai Fong}]}]}}, {"id":2."parent_id":0."name":"Guangdong Province"."children":[
            {
                "id":9."parent_id":2."name":"Dongguan"."children":[
                    {
                        "id":10."parent_id":9."name":"Chang 'an Town"}]}]}, {"id":3."parent_id":0."name":Jiangxi Province."children":[
            {
                "id":11."parent_id":3."name":"Nanchang city"}}]]Copy the code

The implementation code

let array = [
    {
        id: 1.parent_id: 0.name: "Sichuan Province"
    },
    {
        id: 2.parent_id: 0.name: "Guangdong Province"
    },
    {
        id: 3.parent_id: 0.name: Jiangxi Province
    },
    {
        id: 5.parent_id: 1.name: "Chengdu city"
    },
    {
        id: 6.parent_id: 5.name: Jinjiang District
    },
    {
        id: 7.parent_id: 6.name: Nine Eye Bridge
    },
    {
        id: 8.parent_id: 6.name: LAN Kwai Fong
    },
    {
        id: 9.parent_id: 2.name: "Dongguan"
    },
    {
        id: 10.parent_id: 9.name: "Chang 'an Town"
    },
    {
        id: 11.parent_id: 3.name: "Nanchang city"}]function listToTree(list) {
    let map = {};
    list.forEach(item= > {
        if(! map[item.id]) { map[item.id] = item; }}); list.forEach(item= > {
        if(item.parent_id ! = =0) { map[item.parent_id].children ? map[item.parent_id].children.push(item) : map[item.parent_id].children = [item]; }});return list.filter(item= > {
        if (item.parent_id === 0) {
            returnitem; }})}console.log(listToTree(array));
Copy the code

Analysis of the

The core of this code is in the listToTree method, which is divided into three parts:

The first part

The first part starts by copying all the elements in the array into the map (note: this is a reference copy, so this detail is important).

The second part

Map before executing the second traversal:

// map { ... ."3": {"id": 3."parent_id": 0."name":Jiangxi Province},... }Copy the code

Parent_id = 0; parent_id = 0;

[
	...,
	{
		id: 11,
		parent_id: 3,
		name: "Nanchang city"},... ]Copy the code

Map [item.parent_id] = map[item.parent_id];

map["3"].children ? map["3"].children.push(item) : map[3].children = [item];
Copy the code

The above code determines if children exist, assigns a value to it if not, or pushes the value to children.

After the second step, we have added the child node to its parent, but we have not removed the previous child node. So the third part is to filter the data, as long as the parent node.

conclusion

Note that we always operate on the map, but how the result ends up on the list, which is the reference copy mentioned above.