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

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]; вместо возврата массива.

Когда вы строите «функцию построения дерева», вы должны решить, является ли «вещь верхнего уровня» одним элементом или массивом элементов. Поскольку вы сказали 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);

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

Обратите внимание, что это будет работать для 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);