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