JavaScript - 親ノードを再帰的に検索する

Question

JavaScriptを使用しているアプリがあります。このアプリでは、JavaScriptオブジェクトのツリーがあります。このJSFiddleにツリーの例とコードを示します。

祖先であるIDのリストを返す関数を作成しようとしています。特定のIDを持つ要素の先祖。現在、私は以下を持っています：

function getAncestors(childId, branch) { 
    var ancestors = []; 
    for (var i = 0; i < branch.length; i++) { 
    for (var j = 0; j < branch[i].children.length; j++) { 
     if (branch[i].children[j].id === childId) { 
     ancestors.push(branch[i].id); 
     return ancestors; 
     } else { 
     var _ancestors = getAncestors(childId, branch[i].children); 
     for (var k = 0; k < _ancestors.length; k++) { 
      if (ancestors.indexOf(_ancestors[k]) === -1) { 
      ancestors.push(_ancestors[k]); 
      } 
     } 
     } 
    } 
    } 
    return ancestors; 
} 

常に最初の親を返します。ただし、すべての祖先を返すわけではありません。たとえば、JSFiddleでは、[201、2]という順序で配列を取得しようとしています。私は間違って何をしているのか分かりません。私はこれを見つめ続け、それは正しいように見える。しかし、明らかに、それは動作していません。

Answer 1

（反復を使用して）コードを働いている：

function getAncestors(childId, newbranch) { 
    for (var i = 0; i < newbranch.length; i++) { // Search all branches 
     var branch = newbranch[i]; 

     if (branch.id === childId) { 
      return []; 
     } else { 
      if (branch.children && branch.children.length) { 
       var x; 

       if ((x = getAncestors(childId, branch.children)) !== false) { 
        x.push(branch.id) 
        return x; 
       } 
      } 
     } 
    } 

    return false; 
} 

結果：

[201,2] 

編集（短い）

function getAncestors(childId, branch) { 
    var i, ancestors; 

    for (i = 0; !ancestors && branch && i < branch.length; i++) { 
     if (branch[i].id === childId) return []; 
     ancestors = getAncestors(childId, branch[i].children); 
     if (ancestors) ancestors.push(branch[i].id); 
    } 
    return ancestors; 
} 

Answer 2

Array#someと実際の親のコールバックを使用して、反復的かつ再帰的なアプローチを使用できます。アレイを移動させることなく、実際の深さマーカーと

function getParents(id, array) { 
 
    function iter(parents) { 
 
     return function (a) { 
 
      if (a.id === id) { 
 
       result = parents; 
 
       return true; 
 
      } 
 
      return a.children && a.children.some(iter([a.id].concat(parents))); 
 
     }; 
 
    } 
 

 
    var result; 
 
    array.some(iter([])); 
 
    return result; 
 
} 
 

 
var tree = [{ id: 1, name: 'Left', children: [{ id: 100, name: 'C1', children: [{ id: 1000, name: 'C2A', children: [] }, { id: 1001, name: 'D2A', children: [] }, { id: 1002, name: 'C2B', children: [] }] }, { id: 101, name: 'C2', children: [{ id: 2000, name: 'D7B', children: [] }, { id: 2001, name: 'E2A', children: [] }, { id: 2002, name: 'C2X', children: [] }] }] }, { id: 2, name: 'Middle', children: [{ id: 200, name: 'Z1', children: [{ id: 3000, name: 'R2A', children: [] }, { id: 3001, name: 'DYA', children: [] }, { id: 3002, name: 'Q2B', children: [] }] }, { id: 201, name: 'X2', children: [{ id: 4000, name: 'DMA', children: [] }, { id: 4001, name: 'ELA', children: [] }, { id: 4002, name: 'CRX', children: [] }] }] }, { id: 3, name: 'Right', children: [{ id: 300, name: 'Z1', children: [{ id: 5000, name: 'F7A', children: [] }, { id: 5001, name: 'EW5', children: [] }, { id: 5002, name: 'D5B', children: [] }] }, { id: 301, name: 'X2', children: [{ id: 6000, name: 'OMA', children: [] }, { id: 6001, name: 'NLA', children: [] }, { id: 6002, name: 'MRX', children: [] }] }] }]; 
 

 
console.log(getParents(4001, tree));

版。結果は逆になりました。ここで

function getParents(id, array) { 
 
    function iter(depth) { 
 
     return function (a) { 
 
      result[depth] = a.id; 
 
      if (a.id === id) { 
 
       result.length = depth; 
 
       return true; 
 
      } 
 
      return a.children && a.children.some(iter(depth + 1)); 
 
     }; 
 
    } 
 

 
    var result = []; 
 
    return array.some(iter(0)) && result; 
 
} 
 

 
var tree = [{ id: 1, name: 'Left', children: [{ id: 100, name: 'C1', children: [{ id: 1000, name: 'C2A', children: [] }, { id: 1001, name: 'D2A', children: [] }, { id: 1002, name: 'C2B', children: [] }] }, { id: 101, name: 'C2', children: [{ id: 2000, name: 'D7B', children: [] }, { id: 2001, name: 'E2A', children: [] }, { id: 2002, name: 'C2X', children: [] }] }] }, { id: 2, name: 'Middle', children: [{ id: 200, name: 'Z1', children: [{ id: 3000, name: 'R2A', children: [] }, { id: 3001, name: 'DYA', children: [] }, { id: 3002, name: 'Q2B', children: [] }] }, { id: 201, name: 'X2', children: [{ id: 4000, name: 'DMA', children: [] }, { id: 4001, name: 'ELA', children: [] }, { id: 4002, name: 'CRX', children: [] }] }] }, { id: 3, name: 'Right', children: [{ id: 300, name: 'Z1', children: [{ id: 5000, name: 'F7A', children: [] }, { id: 5001, name: 'EW5', children: [] }, { id: 5002, name: 'D5B', children: [] }] }, { id: 301, name: 'X2', children: [{ id: 6000, name: 'OMA', children: [] }, { id: 6001, name: 'NLA', children: [] }, { id: 6002, name: 'MRX', children: [] }] }] }]; 
 

 
console.log(getParents(4001, tree));