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

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

1 голос
/ 14 сентября 2011

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

Itemid
Имя
parentItemId <== элементы верхнего уровня без родителей имеют нулевое значение </p>

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

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

Ответы [ 3 ]

4 голосов
/ 14 сентября 2011 
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]; вместо возврата массива.

0 голосов
/ 14 сентября 2011

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

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

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