Je n'arrive pas à convertir une fonction récursive en une itération.
Considérez la fonction J'ai comme entrée un json similaire à celui-ci: function functionWithIteration (rows) {
var my_stack = [null]
var final_val = []
while( my_stack.length > 0 ) {
var ret_val = []
var first_time = true
var id = my_stack.pop()
var temp_val = []
for (let i = 0; i < rows.length; i++) {
var row = rows[i]
var signal = true
if (id == row.id_parent) {
signal = false
var new_element = {
id: row.id,
id_parent: row.id_parent,
value: row.value,
data: []
}
for (let property in row) {
if (property == 'id' || property == 'id_parent' || property == 'value') {
continue
}
new_element[property] = row[property]
}
if (first_time){
ret_val.push(new_element)
first_time = false
}
else {
ret_val[ret_val.length - 1].data.push(new_element)
}
}
if ( signal) {
temp_val.push(ret_val)
my_stack.push(row.id)
}
}
final_val.push(temp_val)
}
return final_val
}
[{
"id": "c-1",
"id_parent": null,
"value": "Chapter 1",
"data": [{
"id": "a-1",
"id_parent": "c-1",
"value": "Articole 1.1",
"data": []
},
{
"id": "a-2",
"id_parent": "c-1",
"value": "Articole 1.2",
"data": []
}
]
},
{
"id": "c-2",
"id_parent": null,
"value": "Chapter 2",
"data": [{
"id": "a-21",
"id_parent": "c-2",
"value": "Articole 2.1",
"data": []
},
{
"id": "a-22",
"id_parent": "c-2",
"value": "Articole 2.2",
"data": [{
"id": "a-221",
"id_parent": "a-22",
"value": "Quote 221 from article 2.2",
"data": []
},
{
"id": "a-222",
"id_parent": "a-22",
"value": "Quote 222 from article 2.2",
"data": []
},
]
},
]
}
]
3 Réponses :
Vous pouvez adopter une approche en boucle unique avec un objet pour l'identifiant et les parents connus.
Cette solution n'attend pas de données triées.
.as-console-wrapper { max-height: 100% !important; top: 0; }
var data = [{ id: "c-1", id_parent: null, value: "Chapter 1" }, { id: "a-1", id_parent: "c-1", value: "Article 1.1" }, { id: "a-2", id_parent: "c-1", value: "Article 1.2" }, { id: "c-2", id_parent: null, value: "Chapter 2" }, { id: "a-21", id_parent: "c-2", value: "Article 2.1" }, { id: "a-22", id_parent: "c-2", value: "Article 2.2" }, { id: "a-221", id_parent: "a-22", value: "Quote 221 from article 2.2" }, { id: "a-222", id_parent: "a-22", value: "Quote 222 from article 2.2" }],
tree = function (data, root) {
var o = {};
data.forEach(function (a) {
if (o[a.id] && o[a.id].children) {
a.children = o[a.id].children;
}
o[a.id] = a;
o[a.id_parent] = o[a.id_parent] || {};
o[a.id_parent].children = o[a.id_parent].children || [];
o[a.id_parent].children.push(a);
});
return o[root].children;
}(data, null);
console.log(tree);
C'était une réponse utile. Merci!
C'est une solution assez simple une fois que vous avez compris la simple étape de conservation des références aux objets. Faites une boucle sur le tableau et créez un objet avec l'ID d'élément comme clé. Vous pouvez ensuite l'utiliser pour référencer l'élément afin d'ajouter ses enfants.
var data = [{
"id": "c-1",
"id_parent": null,
"value": "Chapter 1"
},
{
"id": "a-1",
"id_parent": "c-1",
"value": "Article 1.1"
},
{
"id": "a-2",
"id_parent": "c-1",
"value": "Article 1.2"
},
{
"id": "c-2",
"id_parent": null,
"value": "Chapter 2"
},
{
"id": "a-21",
"id_parent": "c-2",
"value": "Article 2.1"
},
{
"id": "a-22",
"id_parent": "c-2",
"value": "Article 2.2"
},
{
"id": "a-221",
"id_parent": "a-22",
"value": "Quote 221 from article 2.2"
},
{
"id": "a-222",
"id_parent": "a-22",
"value": "Quote 222 from article 2.2"
}
]
// we use reduce to loop over the object to build up our new object.
var result = data.reduce((obj, itm) => {
// store it into a obj so we can reference it
obj.temp[itm.id] = itm
// check to see if we have a parent
if (itm.id_parent) {
// if we have a parent see if data is set yet
// if not, set it to an empty array
obj.temp[itm.id_parent].data = obj.temp[itm.id_parent].data || []
// push the child into the parent
obj.temp[itm.id_parent].data.push(obj.temp[itm.id])
} else {
// If we have no parent, than it is a root element
// or we push it into an array to keep track of it
obj.order.push(obj.temp[itm.id])
}
// return the object for reduces next iteration
return obj
}, { temp:{}, order:[]}) // init recude with an empty object and array
.order // return the order
console.log(result)
Cette solution s'attend à ce que les parents comparaissent avant leurs enfants. Si ce n'est pas le cas, vous pouvez faire deux ou trois choses. Dans les deux cas, vous créez un objet "temporaire" jusqu'à ce que vous trouviez le vrai.
Je pense qu'il y a une erreur dans votre logique. Lorsqu'elle se reproduit, elle semble recommencer depuis le début. Intuitivement, cela permettrait à l'instance récursive de trébucher exactement dans la même condition qu'auparavant et donc de se répéter à l'infini. (En termes de logique, plusieurs instances imbriquées se retrouvent avec la même valeur pour la variable de boucle i .)
Non, cela ne recommence pas, car le paramètre id aurait changé. Oui, la recherche linéaire des enfants avec le parent respectif n'est pas terriblement efficace, mais ce n'est pas une récursion infinie (tant que l'entrée encode réellement un arbre borné).
Veuillez nous montrer votre tentative de solution de pile.
Aucune quantité de données ne doit être suffisamment grande pour provoquer un débordement de pile lors d'une traversée d'arborescence récursive. Il semble plus probable que votre arbre d'entrée ne soit pas un arbre, mais qu'il contienne une structure circulaire.
@Bergi J'ai ajouté ma tentative de solution de pile. Ma contribution ne donne pas la structure d'un arbre. C'est un json de niveau. La sortie doit être un json à plusieurs niveaux. Mes données d'entrée ont 10000 lignes et cela me donne une erreur de débordement de pile.
Je veux dire une entrée comme
[{id: 1, parent_id: 2}, {id: 2, parent_id: 1}]. C'est un tableau plat codant un graphe circulaire et provoquerait un débordement de pile (ou une erreur de mémoire insuffisante) sur tout code qui suppose un arbre.@Bergi Vous aviez raison. Il y avait une erreur dans mon entrée (structure circulaire) et cela a provoqué l'erreur de débordement de pile. Quoi qu'il en soit, une très grande traversée d'arbre ne pourrait-elle pas donner un débordement de pile lors de l'exécution d'une fonction récursive? Je pense à l'exemple classique avec fonction factorielle (l'itération est préférée à la fonction récursive).
Oui, une entrée très importante peut également provoquer un stackoverflow - par exemple une liste (arbre dégénéré) avec des millions de nœuds. Mais itératif (avec une pile explicite) n'est pas mieux ici: vous obtiendrez toujours une erreur de manque de mémoire sur les petits appareils. Au lieu de cela, utilisez un algorithme avec une carte de recherche comme dans les réponses ci-dessous.