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