Wie kann diese rekursive Funktion gestoppt werden?

Question

Ich habe Javascript Array, wo jedes Element Verweis auf Eltern hat, und sie können geloopt werden (Zirkelverweis). Beispiel:

[ 
     {"id": 1, "firstName": "Macko","parentId": 12}, 
     {"id": 2, "firstName": "Jess","parentId": 1}, 
     {"id": 3, "firstName": "Peter","parentId": 1}, 
     {"id": 4, "firstName": "Lisa", "parentId": 1}, 
     {"id": 5, "firstName": "Megan","parentId": 1}, 
     {"id": 6, "firstName": "John", "parentId": 4}, 
     {"id": 7, "firstName": "Joe", "parentId": 4}, 
     {"id": 8, "firstName": "Matthew","parentId": 2}, 
     {"id": 9, "firstName": "Peter","parentId": 2}, 
     {"id": 10, "firstName": "Dio","parentId": 5}, 
     {"id": 11, "firstName": "Hello","parentId": 5}, 
     {"id": 12, "firstName": "Ana", "parentId": 4} 
] 

I verschachtelte Datenstruktur auf ausgewählte Datensatz basierend schaffen benötigen es im DOM anzuzeigen, die ich durch rekursive Funktion wie unten erreicht (Quelle here)

function getNestedChildren(arr, parent) { 
    var out = [] 
    for(var i in arr) { 
    if(arr[i].parent == parent) { 
     var children = getNestedChildren(arr, arr[i].id) 

     if(children.length) { 
      arr[i].children = children 
     } 
     out.push(arr[i]) 
    } 
    } 
    return out 
} 

Es funktioniert wirklich gut , aber nicht für zirkuläre Datenstrukturen. Die Sache ist, dass ich die Funktionsausführung stoppen muss, bevor sie das Element erreicht, von dem sie gestartet wurde.

Wie kann ich das erreichen?

Answer 1

Die checked Array hält die id s aller Objekte (Eltern) getNestedChildren bereits aufgerufen wurde.

Wenn das id des aktuellen Kindes in diesem Array ist, schließen Sie es nicht als untergeordnetes Element ein.

var arr = [ 
    {"id": 1, "firstName": "Macko","parentId": 12}, 
    {"id": 2, "firstName": "Jess","parentId": 1}, 
    {"id": 3, "firstName": "Peter","parentId": 1}, 
    {"id": 4, "firstName": "Lisa", "parentId": 1}, 
    {"id": 5, "firstName": "Megan","parentId": 1}, 
    {"id": 6, "firstName": "John", "parentId": 4}, 
    {"id": 7, "firstName": "Joe", "parentId": 4}, 
    {"id": 8, "firstName": "Matthew","parentId": 2}, 
    {"id": 9, "firstName": "Peter","parentId": 2}, 
    {"id": 10, "firstName": "Dio","parentId": 5}, 
    {"id": 11, "firstName": "Hello","parentId": 5}, 
    {"id": 12, "firstName": "Ana", "parentId": 4} 
]; 

var getNestedChildren = function(arr, id, checked) { 

    var out = []; 
    for (var i = 0; i < arr.length; i++) { 
    if (arr[i].parentId === id && checked.indexOf(arr[i].id) === -1) { 
     checked.push(id); 
     var children = getNestedChildren(arr, arr[i].id, checked); 
     if (children.length) { 
     arr[i].children = children; 
     } 
     out.push(arr[i]); 
    } 
    } 
    return out; 

}; 

console.log(getNestedChildren(arr, 12, [])); 

Answer 2

Vielleicht so etwas wie dies sollte für Sie arbeiten:

function getNestedChildren(arr, parent, visited_list) { 
    var out = [] 
    for(var i in arr) { 
    if(!(arr[i].id in visited_list) && (arr[i].parentId == parent)) { 

     visited_list[arr[i].id] = true; 
     var children = getNestedChildren(arr, arr[i].id, visited_list) 

     if(children.length) { 
      arr[i].children = children 
     } 
     out.push(arr[i]) 
    } 
    } 
    return out 
} 

nestedList = getNestedChildren(arr, 1, []) 

Answer 3

Sie könnten die Einträge markieren, die Sie bereits besucht haben. Auf dieser Grundlage können Sie die Verarbeitung desselben Elements zweimal überspringen.

Wenn Sie den Elementen die children-Eigenschaft hinzufügen, können Sie diese für diesen Markierungszweck verwenden, sofern Sie diese Eigenschaft auch dann erstellen, wenn ein Element keine untergeordneten Elemente enthält.

Hier arbeitet Code dies zu tun:

function getNestedChildren(arr, parent) { 
 
    var out = []; 
 
    for(var i in arr) { 
 
    if(arr[i].parentId == parent) { 
 
     if (arr[i].children === undefined) { 
 
      arr[i].children = [] 
 
      var children = getNestedChildren(arr, arr[i].id) 
 
      arr[i].children = children 
 
     } 
 
     out.push(arr[i]) 
 
    } 
 
    } 
 
    return out 
 
} 
 

 
var arr = [ 
 
    {"id": 1, "firstName": "Macko","parentId": 12}, 
 
    {"id": 2, "firstName": "Jess","parentId": 1}, 
 
    {"id": 3, "firstName": "Peter","parentId": 1}, 
 
    {"id": 4, "firstName": "Lisa", "parentId": 1}, 
 
    {"id": 5, "firstName": "Megan","parentId": 1}, 
 
    {"id": 6, "firstName": "John", "parentId": 4}, 
 
    {"id": 7, "firstName": "Joe", "parentId": 4}, 
 
    {"id": 8, "firstName": "Matthew","parentId": 2}, 
 
    {"id": 9, "firstName": "Peter","parentId": 2}, 
 
    {"id": 10, "firstName": "Dio","parentId": 5}, 
 
    {"id": 11, "firstName": "Hello","parentId": 5}, 
 
    {"id": 12, "firstName": "Ana", "parentId": 4} 
 
] 
 

 
getNestedChildren(arr, 1) 
 

 
// Output the lengths of the children's arrays 
 
document.body.innerHTML = arr.map(function (item) { 
 
    return 'Item ' + item.id + ' has ' + item.children.length + ' children.' 
 
}).join('<br>')