Генерация вложенного списка из плоского списка с родительскими / дочерними списками в JavaScript

Question

Я создаю веб-приложение, которое должно обрабатывать вложенные географические данные, чтобы они отображались как в виде дерева, но также были доступны для поиска. Необработанные данные выглядят примерно так:

id:1, name:UK
id:2: name: South-East, parentId: 1
id:3: name: South-West, parentId:1
id:4: name: Berkshire, parentId: 2
id:5: name: Reading, parentId: 4

и я хочу, чтобы это выглядело примерно так:

id:1: name UK, children[ 
 {id: 2, name: South-East, children:[
    {id:4: name: Berkshire, children: [
       {id:5: name: Reading}
     ]
  }, 
   {id:3: name: South-West}
]

, чтобы каждое географическое расположение имело свойство массива "children", которое содержит все подобласти, каждая из которых имеет другое свойство массива "children", и так далее. Вероятно, имеет смысл также иметь свойство «parent», чтобы я мог переходить от любого дочернего элемента к его родительскому элементу.

Мне также нужно иметь возможность поиска в списке - поиск по каждой ветви дерева может занять некоторое время, поэтому, возможно, мне нужно также сохранить список в плоском формате.

Я знаю, как я мог бы сделать это в JavaScript (возможно, используя jLinq для фильтрации, группировки и сортировки), но я не знаю, насколько это было бы быстро. Кто-нибудь уже пробовал это сделать в JavaScript или знает какие-нибудь общие алгоритмы / шаблоны, которые решают эту проблему?

Answer 1

На самом деле не так сложно превратить плоский массив в дерево и сделать это довольно быстро, я думаю, что самым медленным будет определение структуры данных на странице (следовательно, ленивая загрузка была успешной!).В этом можно помочь, уменьшив определение структуры данных.

В Javascript я сделал это так:

    //Make the data definition as small as possible..
    //each entry is [ name, parent_pos_in_array]..
    //note: requires that a parent node appears before a child node..
    var data = [
        ["UK", -1], //root..
        ["South-East", 0],
        ["South-West", 0],
        ["Berkshire", 1],
        ["Reading", 3]
        //...etc...
    ];

    //Turns given flat arr into a tree and returns root..
    //(Assumes that no child is declared before parent)
    function makeTree(arr){
        //Array with all the children elements set correctly..
        var treeArr = new Array(arr.length);

        for(var i = 0, len = arr.length; i < len; i++){
            var arrI = arr[i];
            var newNode = treeArr[i] = {
                name: arrI[0],
                children: []
            };
            var parentI = arrI[1];
            if(parentI > -1){ //i.e. not the root..
                treeArr[parentI].children.push(newNode);
            }
        }
        return treeArr[0]; //return the root..
    }

    var root = makeTree(data);

Чтобы проверить скорость в большом списке, вы можете запустить:

    var data = [['root', -1]];
    for(var i = 1; i < 100000; i++){
        var parentI = Math.floor(Math.random()*(i-1));
        data.push(['a_name', parentI]);   
    }
    var start = new Date().getTime();
    var tree = makeTree(data);
    var end = new Date().getTime();

    console.log('Took: ' + (end-start) + 'ms.');

При наличии 100000 элементов в массиве на моем старом рабочем столе требуется <200 мс.Не уверен, что такое представление приемлемо, хотя! </p>

Answer 2

С Lodash:

var index = _.mapKeys(data,'id');
var obj = {};
_.each(index,function(v){
  if(!v.parentId){
    obj[v.id]=v;
  }else{
    if(!index[v.parentId].children){
      index[v.parentId].children=[];
    }
    index[v.parentId].children.push(v);
  }
});

Демоверсия здесь

Answer 3

Если у вас есть простой массив объектов id и parent-id без других подсказок на уровне, создать вложенную форму непросто. Я предполагаю, что рекурсивные подходы не будут практичными в длинных списках. Наилучший метод, который я мог придумать, - это отсортировать массив таким образом, чтобы все дети следовали за своими родителями. Родители и дети, и даже корневые объекты могут быть смешаны, но ребенок должен прийти после своего родителя. Предполагая, что структура объекта похожа на var data = [{id: KL442, pid: HN296}, {id: ST113, pid: HN296}, {id: HN296, pid: "root"},...], тем не менее сортировка является первым этапом работы. При сортировке мы можем создать LUT (таблицу поиска), чтобы получить доступ к родителям практически бесплатно. На выходе из внешнего цикла для этого достаточно одной инструкции lut[a[i].id]=i;. Это делает работу чрезвычайно быстрой на стадии вложения. Это этап сортировки и подготовки LUT.

function sort(a){
  var len = a.length,
      fix = -1;
  for (var i = 0; i < len; i++ ){
      while(!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i) [a[i],a[fix]] = [a[fix],a[i]];
      lut[a[i].id]=i;
  }
  return a;
}

После того, как он отсортирован, единственной вещью, которую вы должны сделать для получения вложенной структуры, является обратная итерация. Теперь, когда ваш массив данных отсортирован и подготовлено LUT, это код для вложения.

for (var i = sorted.length-1; i>=0; i--)
    sorted[i].pid != "root" && (!! sorted[lut[sorted[i].pid]].children
                                && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0])
                                || (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]]));

Для рабочего образца вы можете проверить мой предыдущий ответ .