javascript 如何从 JSON 数据创建树结构

How to create a tree structure from JSON data

提问by Nina Scholz

I have a list in JSON like this one:

我有一个像这样的 JSON 列表：

var arr=[
{
     "text":"text1",
     "id"  :"1",
     //no parent id
 },
{
     "text":"text2",
     "id"  :"2",
     "idParent":"1"
 },
{
     "text":"text3",
     "id"  :"3",
     "idParent":"2"
 },
{
     "text":"text4",
     "id"  :"4",
     "idParent":"1"
 },
{
     "text":"text5",
     "id"  :"5",
      //no parent id
 },
];

And I need to convert that list in a hierarchy tree like the following:

我需要在层次树中转换该列表，如下所示：

var arr = [
  {
    "text": "Parent 1",
    "id"  : "1",
    "nodes": [
      {
        "text": "Child 1",
        "id"  : "2",
        "parentid"  : "1",
        "nodes": [
          {
            "text": "Grandchild 1",
            "id"  : "4",
            "parentid"  : "2",
          },
          {
            "text": "Grandchild 2",
             "id"  : "8",
            "parentid"  : "2",
          }
        ]
      },
      {
        "text": "Child 2",
        "id"  : "10",
        "parentid"  : "1",
      }
    ]
  },
  {
    "text": "Parent 2",
    "id"  : "19",
    //no parent id
  }
];

Only the root parents have no "parentid" element.

只有根父级没有“parentid”元素。

?How can I do this in Javascript?

？我怎样才能在 Javascript 中做到这一点？

Thanks in advance for your help.

在此先感谢您的帮助。

回答by Nina Scholz

A solution for unordered nodes.

无序节点的解决方案。

var arr = [
        { text: "text3", id: "3", parentId: "2" },
        { text: "text2", id: "2", parentId: "1" },
        { text: "text4", id: "4", parentId: "1" },
        { text: "text1", id: "1", /* no parent id */ },
        { text: "text5", id: "5", /* no parent id */ }
    ],
    data = arr.reduce(function (r, a) {
        function getParent(s, b) {
            return b.id === a.parentId ? b : (b.nodes && b.nodes.reduce(getParent, s));
        }

        var index = 0, node;
        if ('parentId' in a) {
            node = r.reduce(getParent, {});
        }
        if (node && Object.keys(node).length) {
            node.nodes = node.nodes || [];
            node.nodes.push(a);
        } else {
            while (index < r.length) {
                if (r[index].parentId === a.id) {
                    a.nodes = (a.nodes || []).concat(r.splice(index, 1));
                } else {
                    index++;
                }
            }
            r.push(a);
        }
        return r;
    }, []);

document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');

回答by László Kardinál

I used an object as a map here, otherwise you must iterate through all the array elements for search for ids of the nodes, and removing elements is easier too. The toString() functions are there, because the keys of the map must be strings.

我在这里使用了一个对象作为映射，否则您必须遍历所有数组元素以搜索节点的 id，并且删除元素也更容易。toString() 函数在那里，因为映射的键必须是字符串。

// we use a map for search for the nodes by their ids
var nodes_map = {};

// we copy all the elements into the map, where the keys are the ids of the nodes
for ( var i=0; i<arr.length; ++i )
{
    // create nodes array for each node
    arr[ i ].nodes = [];

    // copy into the map
    nodes_map[ arr[i].id.toSting() ] = arr[ i ];
}    

// we iterate through all nodes, and add them into their parent's node array
for ( var key in nodes_map )
{
    // current node
    var node = nodes_map[ key ];

    // if the current node have idParent property, and the parent exists in the map
    if ( "idParent" in node && node.idParent.toSting() in nodes_map )
    {
        // we add the current node to the parent's nodes array 
        nodes_map[ node.idParent.toSting() ].nodes.push( node );
    }
}

// we remove all the nodes from the map, that has parents
for ( var key in nodes_map )
{
    // current node
    var node = nodes_map[ key ];

    // if it has idParent property
    if ( "idParent" in node )
    {
        // we remove from the map
        delete nodes_map[ key ];
    }
}    

// results array
var new_arr = [];
// copy back the nodes from the map into an array
for ( var key in nodes_map )
{
    new_arr.push( nodes_map[ key ] );
}