生成嵌套表从平面列表，在JavaScript中的父/子列表 [英] Generating nested list from flat list with parent/child lists in JavaScript

问题描述

我要建一个网络应用程序，需要处理嵌套的地理数据以树状两个显示，也可以进行搜索。原始数据看起来是这样的：

I'm building a web-app that needs to process nested geographical data to both display in a treeview, but also be searchable. The raw data looks something like this:

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

和我希望它看起来是这样的：

and I want it to look something like this:

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}
]

，使得每个的地理位置具有孩子数组属性，它包含了所有的子区域，每个都具有另一个孩子数组属性，等等。或许，这将是有意义的有一个父的属性为好，这样我就可以浏览任何子项到其父母。

so that each geographical location has a "children" array property, which contains all the sub-areas, each of which has another "children" array property, and so on. It would probably make sense to have a "parent" property as well, so I could navigate from any child item up to its parent.

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

I also need to be able to search the list - searching each branch of the tree may take some time, so perhaps I need to also keep the list in flat format.

我知道我是怎样的可以做到这一点在JavaScript（可能使用JLINQ过滤，分组和排序），但我不知道这将是多么快是。有没有人已经有了一展身手的任何一般的算法/模式，解决了这个在这个在JavaScript或不知道？

I know how I could do this in JavaScript (possibly using jLinq for filtering, grouping and sorting), but I don't know how fast it would be. Has anyone already had a go at this in JavaScript or know of any general algorithms/patterns that solve this?

推荐答案

这其实并不难，使平板式成一棵树，做到迅速pretty的，我觉得最慢位将获得的定义数据结构到页面中（所以为什么你懒加载成功了！）。这虽然可以通过使数据结构定义更小的办法。

It's actually not that difficult to make the flat array into a tree and do it pretty quickly, I think the slowest bit will be getting the definition of the data structure onto the page (hence why you're lazy loading was successful!). This can be helped though by making the data structure definition smaller.

在Javascript中我做到了，是这样的：

In Javascript I did it like this:

    //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);

要测试的速度在更大的列表，你可以运行：

To test the speed on a larger list you can run:

    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花＆LT; 200毫秒我的旧桌面上。不知道什么样的表现是可以接受的，但！

With 100000 elements in the array it takes < 200ms on my old desktop. Not sure what kind of performance is acceptable though!

这篇关于生成嵌套表从平面列表，在JavaScript中的父/子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！