在JavaScript中使用父/子列表生成嵌套列表

我正在构建一个需要处理嵌套地理数据以在树视图中显示的Web应用程序，但也是可搜索的。原始数据看起来是这样的：在JavaScript中使用父/子列表生成嵌套列表

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中了解了这个问题，或者知道解决这个问题的一般算法/模式？

来源

2011-02-16 TobyEvans

想通了......延迟加载。我们不需要一次显示所有的数据，只需要按需（这是一个很棒的数据结构，人们将点击进入他们需要的位）。查找相关项目并在需要时将它们添加到“children”属性将会更容易，而不是事先做好整个项目...... – TobyEvans 2011-02-16 13:33:03

您是否介意在下面发布您的解决方案作为答案，以便我们可以解决此问题未经答案的清单？谢谢。 – 2011-07-18 15:44:38

实际上，将平面数组放入树中并很快完成并不困难，我认为最慢的位将获得页面上数据结构的定义（因此，为什么您的延迟加载是成功的！）。尽管通过使数据结构定义更小，这可以得到帮助。

在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的我旧桌面。不知道什么样的表演是可以接受的！

来源

2012-01-20 21:52:59

如果你有一个简单的ID &父级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。

来源

2016-05-16 15:36:35 Redu

在JavaScript中使用父/子列表生成嵌套列表

回答

相关问题