Comment arrêter cette fonction récursive?

Question

J'ai tableau javascript, où chaque élément a référence à parent, et ils peuvent être en boucle (référence circulaire). Exemple:

[ 
     {"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} 
] 

je avais besoin de créer une structure de données imbriqués en fonction enregistrement sélectionné pour l'afficher dans les DOM, que j'obtenus par fonction récursive comme ci-dessous (source 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 
} 

Il fonctionne très bien , mais pas pour les structures de données circulaires. La chose est que j'ai besoin d'arrêter l'exécution de la fonction avant qu'elle n'atteigne l'élément à partir duquel elle a démarré.

Comment puis-je y parvenir?

Answer 1

Le tableau checked maintient les id s de tous les objets (parents) getNestedChildren était déjà mis à contribution.

Si le id de l'enfant actuel figure dans ce tableau, ne l'incluez pas en tant qu'enfant.

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

Peut-être quelque chose comme cela devrait fonctionner pour vous:

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

Vous pouvez marquer les entrées que vous avez déjà visités. En fonction de cela, vous pouvez ignorer le traitement du même élément deux fois. Lorsque vous ajoutez la propriété children aux éléments, vous pouvez l'utiliser à cette fin, à condition de créer également cette propriété lorsqu'un élément n'a pas d'enfants.

code fonctionne ici faire:

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