Convert genitore-figlio array ad albero

Question

Qualcuno può aiutare a convertire il seguente elenco di oggetti padre-figlio:

 
[ 
    { 
     "name":"root", 
     "_id":"root_id", 
    }, 
    { 
     "name":"a1", 
     "parentAreaRef":{ 
     "id":"root_id", 
     }, 
     "_id":"a1_id", 
    }, 
    { 
     "name":"a2", 
     "parentAreaRef":{ 
     "id":"a1_id", 
     }, 
     "_id":"a2_id", 
    }, 
    { 
     "name":"a3", 
     "parentAreaRef":{ 
     "id":"a2_id", 
     }, 
     "_id":"a3_id", 
    }, 
    { 
     "name":"b1", 
     "parentAreaRef":{ 
     "id":"root_id", 
     }, 
     "_id":"b1_id", 
    }, 
    { 
     "name":"b2", 
     "parentAreaRef":{ 
     "id":"b1_id", 
     }, 
     "_id":"b2_id", 
    }, 
    { 
     "name":"b3", 
     "parentAreaRef":{ 
     "id":"b1_id", 
     }, 
     "_id":"b3_id", 
    } 
]

in una struttura ad albero che mostra la relazione genitore-figlio:

 
[ 
    { 
     "name": "root", 
     "_id":"root_id", 
     "children": [ 
      { 
       "name": "a1", 
       "_id":"a1_id", 
       "children" : [ 
        { 
         "name" : "a2", 
         "_id":"a2_id", 
         "children" : [ 
          { 
           "name" : "a3" 
           "_id":"a3_id" 
          } 
         ] 
        } 
       ] 
      }, 
      { 
       "name": "b1", 
       "_id":"b1_id", 
       "children" : [ 
        { 
         "name" : "b2" 
         "_id":"b2_id" 
        }, 
        { 
         "name" : "b3" 
         "_id":"b3_id" 
        } 
       ] 
      } 
     ] 
    } 
] 

(The la struttura di output è una matrice che consente più radici ma se è possibile ottenere una soluzione che gestisca una singola radice è anche ottima.)

L'albero di output è simile al seguente:

 

root 
    | 
    -- a1 
    | | 
    | -- a2 
    |  | 
    |  -- a3 
    | 
    -- b1 
     | 
     -- b2 
     -- b3 

Grazie!

Answer 1

Ho una soluzione che funziona. Posso darti suggerimenti per risolverlo. La cosa buona è che i tuoi dati non contengono alcun riferimento futuro ai nodi. Quindi puoi creare il tuo albero con un solo passaggio attraverso l'array. Se nota, dovrai prima passare attraverso l'intero array per creare una mappa di ID ai nodi.

Il tuo algoritmo sarà simile a questo.

1. Creare una mappa che associa gli ID ai nodi. Ciò renderà più semplice la ricerca dei nodi.
2. Passa attraverso l'array di nodi.
3. Per ogni elemento.
   1. Aggiungere una voce nella mappa.
   2. Aggiungere una proprietà children (un array) a questo nodo.
   3. L'elemento ha un genitore? In caso contrario, deve essere la radice, quindi assegnare questo elemento alla radice dell'albero.
   4. Questo elemento ha un genitore, quindi cerca il nodo genitore, quindi aggiungi questo nodo corrente come figlio del nodo genitore (aggiungilo all'array children).

Questo dovrebbe aiutare a risolvere il problema. Se stai riscontrando problemi specifici con questo algoritmo, posso indicare dove sono i problemi e come risolverlo o pubblicare la soluzione e spiegare come l'ho risolto.

UPDATE

ho guardato la soluzione che avete. In realtà non hai bisogno di ricorsione per questo e puoi farlo in modo iterativo usando l'algoritmo che ho descritto sopra. Stai anche modificando la struttura sul posto, il che rende l'algoritmo più complicato. Ma sei un po 'sulla buona strada. Ecco come ho risolto:

var idToNodeMap = {}; //Keeps track of nodes using id as key, for fast lookup 
var root = null; //Initially set our loop to null 

//loop over data 
data.forEach(function(datum) { 

    //each node will have children, so let's give it a "children" poperty 
    datum.children = []; 

    //add an entry for this node to the map so that any future children can 
    //lookup the parent 
    idToNodeMap[datum._id] = datum; 

    //Does this node have a parent? 
    if(typeof datum.parentAreaRef === "undefined") { 
     //Doesn't look like it, so this node is the root of the tree 
     root = datum;   
    } else {   
     //This node has a parent, so let's look it up using the id 
     parentNode = idToNodeMap[datum.parentAreaRef.id]; 

     //We don't need this property, so let's delete it. 
     delete datum.parentAreaRef; 

     //Let's add the current node as a child of the parent node. 
     parentNode.children.push(datum);   
    } 
}); 

ora root punti per l'intero albero.

Fiddle.

Per il caso in cui la matrice di elementi è in ordine arbitrario, è necessario inizializzare prima idToNodeMap.Il resto dell'algoritmo rimane più o meno lo stesso (tranne che per la linea in cui si memorizza il nodo della mappa, che non è necessaria perché l'avete fatto già nel primo passaggio):

var idToNodeMap = data.reduce(function(map, node) { 
    map[node._id] = node; 
    return map; 
}, {});