JavaScriptツリー - エレガントなソリューションですか？

Question

私は例えば、複数のツリーを持っています。このような単一のJavaScriptオブジェクトで表現

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

：

{ '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 } 

すなわち、すべてのノードがキーとして表示され、特定のキーの値/ nodeはすべての子ノードの配列です（子ノードがない場合はnull）。

私は二つのことを構築したいと思います：

1. すべての根の配列を。この例では、['a', 'h']

2. すべてのルートについて、ルートを含むすべての子孫の配列。この例では：

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

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

得られた配列内の要素の順序は問いません。

JavaScriptでこれを実装するための洗練された方法を提案できますか（jQueryは許可されています）。

Answer 1

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変数は、あなたの2番目のタスクについては、次の値が含まれています

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

そして、あなたの最初の仕事Object.keys(roots)戻って必要な配列のために。

Answer 2

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