在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中使用父/子列表生成嵌套列表

回答

相關問題