將樹狀結構轉換爲分層陣列

Question

我對這個問題困惑了好幾個小時。我正在使用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"}, 
] 

Answer 1

我會在這裏使用遞歸來「走」下樹。請注意，您的輸入樹有時使用「children」，有時使用「節點」來表示其子數組;我在整個過程中都將它改爲「小孩」。

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>

Answer 2

一個簡單的遞歸函數將做的工作：

var out = [ 
]; 
var generate = function (collection, parent) { 
    for (var i = 0; i < collection.length; i++) { 
    var obj = { 
     '_id': collection[i]['_id'], 
     'title': collection[i]['title'], 
     'parentId': parent ? parent['_id'] : null, 
     'path': parent ? ',' + parent['_id'] : '' 
    }; 
    out.push(obj); 
    if (collection[i].nodes) { 
     generate(collection[i].nodes, collection[i]); 
    } else { 
     generate(collection[i].children, collection[i]); 
    } 
    } 
}; 

見下面的例子：

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': [ 
     ] 
     } 
    ] 
    } 
]; 
var out = [ 
]; 
var generate = function (collection, parent) { 
    for (var i = 0; i < collection.length; i++) { 
    var obj = { 
     '_id': collection[i]['_id'], 
     'title': collection[i]['title'], 
     'parentId': parent ? parent['_id'] : null, 
     'path': parent ? ',' + parent['_id'] : '' 
    }; 
    out.push(obj); 
    if (collection[i].nodes) { 
     generate(collection[i].nodes, collection[i]); 
    } else { 
     generate(collection[i].children, collection[i]); 
    } 
    } 
}; 
generate(tree, null); 
console.log(JSON.stringify(out,null,4)); 
//prints 

[ 
    { 
     "_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": ",11" 
    }, 
    { 
     "_id": 1111, 
     "title": "node1.1.1.1", 
     "parentId": 111, 
     "path": ",111" 
    }, 
    { 
     "_id": 12, 
     "title": "node1.2", 
     "parentId": 1, 
     "path": ",1" 
    }, 
    { 
     "_id": 2, 
     "title": "node2", 
     "parentId": null, 
     "path": "" 
    }, 
    { 
     "title": "node2.1", 
     "parentId": 2, 
     "path": ",2" 
    }, 
    { 
     "_id": 22, 
     "title": "node2.2", 
     "parentId": 2, 
     "path": ",2" 
    }, 
    { 
     "_id": 3, 
     "title": "node3", 
     "parentId": null, 
     "path": "" 
    }, 
    { 
     "title": "node3.1", 
     "parentId": 3, 
     "path": ",3" 
    }, 
    { 
     "_id": 4, 
     "title": "node4", 
     "parentId": null, 
     "path": "" 
    }, 
    { 
     "_id": 41, 
     "title": "node4.1", 
     "parentId": 4, 
     "path": ",4" 
    } 
]