JavaScript樹 - 優雅的解決方案？

我有多個樹，例如：JavaScript樹 - 優雅的解決方案？

a     h 
| \    | 
b c    i 
/| \   /\ 
d e f   j k 
    |   /| \ 
    g   l m n

，其在一個單一的JavaScript對象像這樣表示：

{ 'a': ['b', 'c'], 
    'b': null, 
    'c': ['d', 'e', 'f'], 
    'd': null, 
    'e': ['g'], 
    'f': null, 
    'g': null, 
    'h': ['i'], 
    'i': ['j', 'k'], 
    'j': ['l', 'm', 'n'], 
    'k': null, 
    'l': null, 
    'm': null, 
    'n': null }

即所有節點顯示爲鍵，和一個特定的鍵的值/節點是其所有子節點的數組（如果它沒有子節點，則爲null）。

我想構建兩件事情：

所有根的數組。在此示例中：['a', 'h']
對於每個根，其所有後代的數組（包括根）。在這個例子中：

['a', 'b', 'c', 'd', 'e', 'f', 'g']

['h', 'i', 'j', 'k', 'l', 'm', 'n']

在所得陣列元素的順序並不重要。

你能否提出一個優雅的方法來在JavaScript中實現這一點（允許使用jQuery）。

來源

2012-02-17 Misha Moroshko

任何你需要遍歷整個樹，除非你實現某種緩存子樹結果。這些樹有多大？你是否已經嘗試過遍歷整棵樹的最古老的方法？ – Eduardo 2012-02-17 09:41:48

jQuery適用於dom操作。它提供的邏輯代碼很少（我只能想到'map'）。你有沒有考慮過underscore.js？它是一個庫，通過爲普通JavaScript提供有用的工具而不是DOM的東西來補充jQuery。 – 2012-02-17 09:42:04

典型的深度爲3，孩子的數量少於5. – 2012-02-17 09:47:50

var src = { 'a': ['b', 'c'], 
    'b': null, 
    'c': ['d', 'e', 'f'], 
    'd': null, 
    'e': ['g'], 
    'f': null, 
    'g': null, 
    'h': ['i'], 
    'i': ['j', 'k'], 
    'j': ['l', 'm', 'n'], 
    'k': null, 
    'l': null, 
    'm': null, 
    'n': null }; 

/* ******************************************************************* */ 

var roots={},p1,p2,isRoot,i=-1; 
for(p1 in src){ 
    isRoot=true; 
    for(p2 in src)if(src[p2]&&src[p2].indexOf(p1)>-1){isRoot=false;break;} 
    if(isRoot)roots[p1]=[p1]; 
} 
for(p1 in roots){ 
    i=-1; 
    while(++i<roots[p1].length) 
     if(src[roots[p1][i]]&&src[roots[p1][i]].length) 
      Array.prototype.push.apply(roots[p1],src[roots[p1][i]]); 
}

結果roots變量包含未來價值爲你的第二個任務：

roots: { 
     "a": ["a", "b", "c", "d", "e", "f", "g"], 
     "h": ["h", "i", "j", "k", "l", "m", "n"] 
    }

併爲您的第一項任務Object.keys(roots)回報需要陣列。

來源

2012-02-17 13:20:00

var tree = {...}; 
var roots = [], rootdescendants = {}; 
tl: for (var p in tree) { // tree-loop 
    for (var r in rootdescendants) 
     // check if p is already in one of the result arrays 
     if (rootdescendants[r].lastIndexOf(p)>-1) 
      continue tl; 
    var d = rootdescendants[p] = [p]; // create new descendants array 
    for (var i=0; i<d.length; i++) { 
     var c = d[i]; 
     if (i>0 && c in rootdescendants) { // there is already an array for c 
      i += rootdescendants[c].unshift(i, 1) - 3; 
      Array.prototype.splice.apply(d, rootdescendants[c]); // insert into d 
      delete rootdescendants[c]; 
     } else { 
      if (tree[c]) // not null 
       Array.prototype.push.apply(d, tree[c]); 
     } 
    } 
} 
roots = Object.keys(rootdescendants);

來源

2012-02-17 14:43:53 Bergi

JavaScript樹 - 優雅的解決方案？

回答

相關問題