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

Question

我正在构建一个网络应用程序，它需要处理嵌套的地理数据以显示在 TreeView 中，但也可以搜索。原始数据看起来像这样:

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”数组属性，以此类推。拥有一个“父”属性可能也很有意义，这样我就可以从任何子项导航到它的父项。

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

我知道我如何可以在 JavaScript 中执行此操作(可能使用 jLinq 进行过滤、分组和排序)，但我不知道它会多快。有没有人已经在 J​​avaScript 中尝试过这个或者知道解决这个问题的任何通用算法/模式？

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 毫秒。虽然不确定什么样的性能是可以接受的!