Построение графа объекта из плоского массива объектов в JavaScript

Question

У меня есть яваскрипт массив объектов с объектами, которые выглядят так:

Itemid
имя
parentItemId < == элементы верхнего уровня, не имеющие родителей, имеют null значение

Я хочу построить график, в котором родительские элементы содержат массивы детей, а у этих детей есть массивы детей, если это применимо.

Что такое хороший способ сделать это?

Answer 1

function objectGraph(items) 
{ 
    var items_by_id = {}; 
    var roots = []; 
    var i; 

    // Build an id->object mapping, so we don't have to go hunting for parents 
    for (i = 0; i < items.length; ++i) { 
     items_by_id[items[i].itemId] = items[i]; 
     items[i].children = []; 
    } 

    for (i = 0; i < items.length; ++i) { 
     var parentId = items[i].parentItemId; 
     // If parentId is null, this is a root; otherwise, it's parentId's kid 
     var nodes = (parentId === null) ? roots : items_by_id[parentId].children; 
     nodes.push(items[i]); 
    } 
    return roots; 
} 

Примечание Этот код дает каждому узлу children свойство, что пусто, если узел не имеет детей. Я лично считаю его более простым и последовательным, чем каждый узел, возможно, или, может быть, не имея детей; вы можете перебрать children, не беспокоясь о том, существует ли он. У листового узла будет children.length == 0.

Если вы можете гарантировать, что у вас есть ровно один корень, вы можете return roots[0]; вместо возврата массива.

Answer 2

Это немного грубо, но это должно сработать, если я правильно собираю ваш вопрос. Он должен возвращать массив объектов верхнего уровня, у которых их дети правильно организованы под ними.

В качестве примечания, это будет работать для объектов уровня N, а не только на одном уровне.

var finalArray = []; 
var YOUR_RAW_ARRAY = []; 

var buildObjectGraph = function(inputArray){ 
    var i = 0, len = inputArray.length; 
    var returnVal = []; 

    for(;i<len;i++){ 
     if(inputArray[i].parentItemId === null){ 
      findChildren(inputArray[i], inputArray); 
      returnVal.push(inputArray[i]); 
     } 
    } 

    var findChildren = function(root){ 
     var i = 0, i2 = 0, len = rawDataArray.length, len2 = 0; 

     for(;i<len;i++){ 
      if(inputArray[i].parentItemId === root.itemId){ 
       if(root.children){ 
        root.children.push(inputArray[i]); 
       }else{ 
        root.children = []; 
        root.children.push(inputArray[i]); 
       } 
      } 
     } 

     //now call it recursively 
     len2 = root.children.length; 
     if(len2 > 0){ 
      for(;i2 < len2; i2++){ 
       findChildren(root.children[i2]); 
      } 
     } 
    }; 
    return returnVal; 
}; 

//Then execute it 
finalArray = buildObjectGraph(YOUR_RAW_ARRAY); 

Answer 3

Когда вы создаете «функцию строителя дерева», вам нужно решить, является ли «элемент верхнего уровня» единственным элементом или массивом элементов. Поскольку вы сказали itemS, мы идем с массивом. Разница - это параметр, который вы передаете и возвращаетесь обратно, если его массив передается parentId, иначе мы передаем идентификатор.

function buildTree(parentId, list) { 
    var nodes = []; 
    for (var i=0, l; l = list[i]; i++) { 
    if (l.parentId === parentId) { 
// if you need "myList" intact afterwards remove the next line at the cost of efficiency 
     list.splice(i, 1); i--; 
     nodes.push({ 
     id: l.id 
     ,parentId: l.parentId 
     ,name: l.name 
     ,children: buildTree(l.id, list) 
     }); 
    } 
    } 
    return nodes; 
} 

var myTree = buildTree(null, myList);