Algo找到深度并按顺序插入JSON数组

I have requirement to find relationship from json array based on parentId and insert into array in sequential structure . ParentId maps to _Id which is parent .

我要求基于parentId从json数组中找到关系，并在顺序结构中插入到数组中。 ParentId映射到_Id，即父级。

[{"_Id":1,parentId:"",name:'A'},
{"_Id":4,parentId:2,name:'D'},
{"_Id":2,parentId:1,name:'B'},
{"_Id":5,parentId:3,name:'E'},
{"_Id":3,parentId:1,name:'C'}]

The above array need to be converted as below structure with depth field.

上述数组需要转换为具有深度字段的以下结构。

[{"_Id":1,parentId:"",name:'A', 'depth':1},   
{"_Id":2,parentId:1,name:'B', 'depth':2},
{"_Id":4,parentId:2,name:'D', 'depth':3},
{"_Id":3,parentId:1,name:'C', 'depth':2},
{"_Id":5,parentId:3,name:'E', 'depth':3}]

1
    2
        4
    3   
        5

I am a novice programmer and need hint.

我是一名新手程序员，需要提示。

  var finalArray = [];
 var initPath = function (task) {
     // TODO
 };
 for (var i = 0, len = array.length; i < len; i++) {
     if (array[i].parentId == "") {
         array[i]['depth'] = 1;
         finalArray(array[i]);
         initPath(array[i]);
     }
 }

3 个解决方案

#1

Well I won't do all your work for you, but here is a solution that adds the depths without rearranging the order of the elements. It's on JSFiddle, and here's the relevant code:

好吧，我不会为你完成所有工作，但这里有一个解决方案，可以在不重新排列元素顺序的情况下添加深度。它在JSFiddle上，这是相关的代码：

var addDepth = function(data) {
    var depth = 0, nodes = data.filter(function(item) {
        return item.parentId == "";
    }), total = nodes.length;

    do {
        depth++;
        nodes.forEach(function(node) {node.depth = depth;});
        var ids = nodes.map(function(item) {return item["_Id"];});
        nodes = data.filter(function(item) {
            return ids.indexOf(item.parentId) > -1;
        });
        total += nodes.length
    } while (nodes.length > 0 && total <= data.length);
    return data;
};

Note that this changes the array in place, and doens't create a clone. That might or might not be what you want. (As I've focused on functional programming recently, it at least slightly offends my own sensibilities.) This should be relatively easy to change.

请注意，这会更改阵列，并且不会创建克隆。那可能是也可能不是你想要的。 （由于我最近专注于函数式编程，它至少会略微冒犯我自己的敏感性。）这应该相对容易改变。

Note that this is actually my second version. The first one is to my mind much more elegant. But it's based on the Ramda library I'm still developing. While I like the library, and find it easy to use, I would not necessarily expect this code to be more obvious to those who don't do a lot of functional programming:

请注意，这实际上是我的第二个版本。第一个是我的想法更优雅。但它基于我正在开发的Ramda库。虽然我喜欢这个库，并且发现它易于使用，但对于那些没有进行大量函数式编程的人来说，我不一定希望这些代码更加明显：

var addDepth = function(data) {
    var depth = 0, nodes = filter(pipe(get("parentId"), eq("")), data), 
        total = nodes.length;
    do {
        depth++;
        nodes.forEach(function(node) {node.depth = depth;});
        nodes = filter(pipe(get("parentId"), flip(contains)(pluck("_Id", nodes))), data);
        total += nodes.length
    } while (nodes.length > 0 && total <= data.length);
    return data;
};

#2

Well, you can find the root(s) easy enough: they have no parentId. Once you have the root(s), you can find all depth 2 nodes: anything whose parent is a root. Taking this further: a node is at depth n if its parent is at depth n-1 (roots being a special case). Keep looking until everything has a depth assigned to it.

好吧，你可以很容易地找到根目录：它们没有parentId。获得根后，可以找到所有深度为2的节点：父节点为根的任何节点。进一步考虑：如果节点的父节点位于深度n-1（根是特殊情况），则节点位于深度n处。继续观察，直到所有内容都分配给它。

#3

The following method will recursively traverse the tree and add 1 to the count each time it goes down another level. It really isn't the most efficient way of doing so, but in my opinion it is the easiest.

以下方法将递归遍历树，并在每次下降到另一个级别时将计数加1。这真的不是最有效的方式，但在我看来这是最简单的方法。

var array = [{"_Id":1,parentId:"",name:'A'},
{"_Id":4,parentId:2,name:'D'},
{"_Id":2,parentId:1,name:'B'},
{"_Id":5,parentId:3,name:'E'},
{"_Id":3,parentId:1,name:'C'}];

for(var i=0;i<array.length;i++) {
  array[i]["depth"] = findDepth(array[i]);   
}

function findDepth(item) {
    if(item.parentId==="")
        return 1;
    for(var i=0;i<array.length;i++) {
        if(array[i]._Id===item.parentId)
            return 1+findDepth(array[i]);
    }
}