javascript - 将树结构转换为分层数组

这个问题让我困惑了好几个小时。我正在使用Angular和angular-ui-tree来创建具有可编辑数目不多的叶子的树。
我需要展平并将树转换为分层数组，以将其传递给MongoDb。我也正在使用Underscore.js作为实用程序

var tree = [{
    "_id": 1,
        "title": "node1",
        "nodes": [{
        "_id": 11,
            "title": "node1.1",
            "nodes": [{
            "_id": 111,
                "title": "node1.1.1",
                "children": [{
                    "_id": 1111,
                    "title": "node1.1.1.1",
                    "children": []
                }]
        }]
    }, {
        "_id": 12,
            "title": "node1.2",
            "children": []
    }]
}, {
    "_id": 2,
        "title": "node2",
        "children": [{
        "id": 21,
            "title": "node2.1",
            "children": []
    }, {
        "_id": 22,
            "title": "node2.2",
            "children": []
    }]
}, {
    "_id": 3,
        "title": "node3",
        "children": [{
        "id": 31,
            "title": "node3.1",
            "children": []
    }]
}, {
    "_id": 4,
        "title": "node4",
        "children": [{
        "_id": 41,
            "title": "node4.1",
            "children": []
    }]
}]

//desired output
//parentId is null for top leaf nodes, path is String made by the parents' ids


[
    { "_id": 1, "title": "node1", "parentId": null, "path" : ""},
    { "_id": 11, "title": "node1.1", "parentId": 1, "path" : ",1"},
    { "_id": 111, "title": "node1.1.1", "parentId": 11, "path" : ",1,11"},
    { "_id": 1111, "title": "node1.1.1.1", "parentId": 111, "path" : ",1,11,111"},
    { "_id": 12, "title": "node1.1", "parentId": 1, "path" : ",1"},

    { "_id": 2, "title": "node2", "parentId": null, "path" : ""},
    { "_id": 21, "title": "node2.1", "parentId": 2, "path" : ",2"},

    { "_id": 3, "title": "node3", "parentId": null, "path" : ""},
    { "_id": 31, "title": "node3.1", "parentId": 3, "path" : ",3"},

    { "_id": 4, "title": "node4", "parentId": null, "path" : ""},
    { "_id": 41, "title": "node4.1", "parentId": 4, "path" : ",4"},
]

最佳答案

我会在这里使用递归来“沿着树走下去”。请注意，您的输入树有时使用“子代”，有时使用“节点”来表示其子代阵列；我一直将其更改为“儿童”。

var wholeTree = [{
    "_id": 1,
        "title": "node1",
        "children": [{
        "_id": 11,
            "title": "node1.1",
            "children": [{
            "_id": 111,
                "title": "node1.1.1",
                "children": [{
                    "_id": 1111,
                    "title": "node1.1.1.1",
                    "children": []
                }]
        }]
    }, {
        "_id": 12,
            "title": "node1.2",
            "children": []
    }]
}, {
    "_id": 2,
        "title": "node2",
        "children": [{
        "id": 21,
            "title": "node2.1",
            "children": []
    }, {
        "_id": 22,
            "title": "node2.2",
            "children": []
    }]
}, {
    "_id": 3,
        "title": "node3",
        "children": [{
        "id": 31,
            "title": "node3.1",
            "children": []
    }]
}, {
    "_id": 4,
        "title": "node4",
        "children": [{
        "_id": 41,
            "title": "node4.1",
            "children": []
    }]
}];


var flattened = flattenTreeToNodes( wholeTree, null, "" );
$("#output").text( JSON.stringify(flattened) );


function flattenTreeToNodes( tree, parentId, basePath ) {
  console.log( parentId, basePath );
  function createFlattenedNode( treeNode ) {
    var path = parentId?basePath + "," + parentId:"";
    return {
       "_id": treeNode._id,
       title: treeNode.title,
       parentId: parentId,
       path: path
    }
  }

  var nodes = [];
  for(var i=0; i<tree.length; i++) {
     var treeNode = tree[i];
     var flattenedNode = createFlattenedNode(treeNode);
     nodes.push ( flattenedNode );
     var flattenedChildren = flattenTreeToNodes( treeNode.children, treeNode._id, flattenedNode.path );
     nodes = nodes.concat( flattenedChildren );
  }
  return nodes;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<pre id='output'>
</pre>