JavaScript - rekursiv finden Elternknoten

Question

Ich habe eine App mit JavaScript geschrieben. In dieser App habe ich einen Baum von JavaScript-Objekten. Ein Beispielbaum und der folgende Code sind in dieser JSFiddle zu sehen.

Ich versuche, eine Funktion zu schreiben, die eine Liste der IDs zurückgibt, die die Vorfahren sind. Die Vorfahren eines Elements mit einer bestimmten ID. Derzeit habe ich folgendes:

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

Es gibt immer das erste Elternteil zurück. Es gibt jedoch nicht alle Vorfahren zurück. Zum Beispiel versuche ich in der JSFiddle, ein Array, das enthält: [201, 2], in dieser Reihenfolge. Ich bin mir nicht sicher, was ich falsch mache. Ich starre weiter und es sieht korrekt aus. Aber offensichtlich funktioniert es nicht.

Answer 1

Hier arbeitet Code (mit Iteration):

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

Ergebnis:

[201,2] 

Edit (kürzer)

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

Sie könnten einen iterativen und rekursiven Ansatz mit einem Rückruf für Array#some und die tatsächlichen Eltern verwenden.

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

Version ohne eine Anordnung zu bewegen, aber mit einem Marker für die tatsächliche Tiefe. Das Ergebnis ist jetzt umgekehrt.

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