Дерево из ассоциативного массива

Question

Существует массив:

let docs = [  
    { "_id":"1", parent:"_", "title":"one"}, 
    { "_id":"2", parent:"1", "title":"two"}, 
    { "_id":"4", parent:"_", "title":"title"}, 
    { "_id":"5", parent:"4", "title":"www"}, 
    {"_id":"_", "name":"root" }, 
]; 

Мне нужно, чтобы выйти из него, что это дерево:

{'_id':'_','name':'root','child': 
    [ 
     {'_id':'1','parent':'_','title':'one','child': 
      [ 
       {'_id':'2','parent':'1','title':'two','child':[]} 
      ] 
     }, 
     {'_id':'4','parent':'_','title':'title','child': 
      [ 
       {'_id':'6','parent':'4','title':'vvv','child':[]} 
      ] 
     } 
    ] 
} 

Но мой код работает только если родительский элемент всегда выше в списке, чем дети, и я хочу сделать эту работу повсеместно.

Это код:

let node = {}; 
for (let doc of docs) {  
    doc.child = []; 
    node[doc._id] = doc; 

    if (typeof doc.parent === "undefined") 
     tree = doc; 
    else 
     node[doc.parent].child.push(doc); 
} 

console.log('tree->', JSON.stringify(tree)); 

код на codepen: http://codepen.io/alex183/pen/OWvrPG?editors=0112

Answer 1

Вы можете создать рекурсивную функцию с помощью reduce

let docs = [  
 
    { "_id":"1", parent:"_", "title":"one"}, 
 
    { "_id":"2", parent:"1", "title":"two"}, 
 
    { "_id":"4", parent:"_", "title":"title"}, 
 
    { "_id":"5", parent:"4", "title":"www"}, 
 
    {"_id":"_", "name":"root" } 
 
]; 
 

 
function makeTree(data, parent = undefined) { 
 
    return data.reduce(function(r, e) { 
 
    if (e.parent == parent)(e.child = makeTree(data, e._id), r.push(e)) 
 
    return r; 
 
    }, []) 
 
} 
 

 
console.log(makeTree(docs))

Answer 2

Быстрый и грязный способ заключается в использовании функции сортировки.

docs = docs.sort((a, b) => (a._id - b._id)); 

Answer 3

Это предложение с Array#reduce и Map. Он сортирует массив заранее.

var docs = [{ _id: "1", parent: "_", title: "one" }, { _id: "2", parent: "1", title: "two" }, { _id: "4", parent: "_", title: "title" }, { _id: "5", parent: "4", title: "www" }, { _id: "_", name: "root" }], 
 
    order = { undefined: -2, _: -1 }, 
 
    tree = docs 
 
     .sort((a, b) => (order[a.parent] || a.parent) - (order[b.parent] || b.parent) || a._id - b._id) 
 
     .reduce(
 
      (m, a) => (
 
       m 
 
        .get(a.parent) 
 
        .push(Object.assign({}, a, { child: m.set(a._id, []).get(a._id) })), 
 
       m 
 
      ), 
 
      new Map([[undefined, []]]) 
 
     ) 
 
     .get(undefined); 
 

 
console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }