Algo查找深度并在JSON数组中按顺序插入

Question

我需要从基于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'}]

上述阵列需要转换为具有深度场的以下结构。

[{"_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

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

  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]);
     }
 }

Answer 1

我不会为您做所有的工作，但这里有一个解决方案，可以在不重新排列元素顺序的情况下添加深度。它位于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;
};

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

请注意，这实际上是我的第二个版本。在我看来，第一个要优雅得多。但它是基于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;
};

Answer 2

好吧，你可以很容易地找到根：它们没有parentId。一旦有了根，就可以找到所有深度2节点：任何其父节点是根的节点。更进一步地说：如果一个节点的父节点位于深度n-1，则它位于深度n（根是一种特殊情况）。继续寻找，直到所有东西都有一个指定的深度。

Answer 3

以下方法将递归遍历树，并在每次计数下降到另一个级别时将其加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]);
    }
}