使用JavaScript中的父/子列表从平面列表生成嵌套列表

问题描述 投票:3回答:3

我正在构建一个Web应用程序,需要处理嵌套的地理数据,以便在树视图中显示,但也可以搜索。原始数据看起来像这样:

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”数组属性,它包含所有子区域,每个子区域都有另一个“子”数组属性,依此类推。拥有“父”属性可能也是有意义的,因此我可以从任何子项导航到其父项。

我还需要能够搜索列表 - 搜索树的每个分支可能需要一些时间,所以也许我还需要将列表保持为平面格式。

我知道如何在JavaScript中执行此操作(可能使用jLinq进行过滤,分组和排序),但我不知道它会有多快。有没有人已经在JavaScript中找到了这个或知道解决这个问题的任何通用算法/模式?

javascript algorithm
3个回答
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个元素,在我的旧桌面上需要<200ms。不确定哪种表现是可以接受的!


0
投票

如果你有一个简单的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]]));

对于工作样本,您可以检查a previous answer of mine


0
投票

随着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);
  }
});

Demo is here

© www.soinside.com 2019 - 2024. All rights reserved.