Как остановить эту рекурсивную функцию?

Question

У меня есть массив javascript, где каждый элемент имеет ссылку на родителя, и они могут быть закольцованы (круговая ссылка). Пример:

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

мне нужно создать вложенную структуру данных на основе выбранной записи, чтобы отобразить его в DOM, который я достигнутой рекурсивной функции, как показано ниже (источник 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 
} 

Это работает очень хорошо , но не для круговых структур данных. Дело в том, что мне нужно прекратить выполнение функции до того, как она дойдет до элемента, с которого она началась.

Как я могу это достичь?

Answer 1

checked массив хранит id S всех объектов (родителей) getNestedChildren уже призвали.

Если текущий ребенок id находится в этом массиве, не включайте его в качестве дочернего.

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

Возможно, что-то, как это должно работать для вас:

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

Можно отметить записи, которые вы уже посетили. Исходя из этого, вы можете пропустить обработку одного и того же элемента дважды.

Поскольку вы добавляете к элементам свойство children, вы можете использовать это для этой цели маркировки, при условии, что вы также создадите это свойство, когда элемент не имеет детей.

Вот рабочий код делает это:

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