J'essaie donc d'écrire une fonction récursive qui prend un tableau plat d'objets avec leur valeur, leur id et l'id de leur nœud parent et le transforme en une structure arborescente, où les enfants de la structure sont un tableau de nœuds. Les enfants doivent être triés par id et si son null cela peut être le nœud racine.
La fonction im essayant d'écrire la fonction toTree (data), ne devrait prendre que le tableau de données. Je n'ai pas pu le faire sans un parent. Ce que j'ai jusqu'à présent, c'est une fonction (ci-dessous) qui prend les données et le parent pour commencer.
input:
{
id: 1,
parent: null,
value: 'Make Breakfast',
children: [
{
id: 2,
parent: 1,
value: 'Brew coffee',
children: [
{ id: 3, parent: 2, value: 'Boil water' },
{ id: 4, parent: 2, value: 'Grind coffee beans' },
{ id: 5, parent: 2, value: 'Pour water over coffee grounds' }
]
}
]
}
funciton toTree(data) {
customtoTree (data, null);
}
function customToTree (data, parent) {
const out = [];
data.forEach((obj) => {
if (obj.parent === parent) {
const children = customToTree(data,obj.parent);
if (children.length) {
obj[children[0]] = children;
}
const {id,parent, ...content} = obj;
out.push(content);
}
});
return out;
}
output:
const tasks = [
{ id: 1, parent: null, value: 'Make breakfast' },
{ id: 2, parent: 1, value: 'Brew coffee' },
{ id: 3, parent: 2, value: 'Boil water' },
{ id: 4, parent: 2, value: 'Grind coffee beans' },
{ id: 5, parent: 2, value: 'Pour water over coffee grounds' }
];
Je voudrais vraiment comprendre la logique correcte sur la façon de faire cela et y réfléchir et comment le faire sans donner explicitement à un parent.
3 Réponses :
Je n'ai pas pu vérifier plus de cas de test, mais c'est quelque chose que j'ai rapidement pu trouver et qui réussit votre cas d'utilisation, cela ne semble pas si bon, je recommanderais de l'utiliser comme structure initiale, puis de construire dessus . De plus, je suppose que les tâches sont triées par ordre croissant par parent, c'est-à-dire que l'enfant n'apparaîtra qu'après son parent dans le tableau des tâches
const tasks = [
{ id: 1, parent: null, value: 'Make breakfast' },
{ id: 2, parent: 1, value: 'Brew coffee' },
{ id: 3, parent: 2, value: 'Boil water' },
{ id: 4, parent: 2, value: 'Grind coffee beans' },
{ id: 5, parent: 2, value: 'Pour water over coffee grounds' },
{ id: 6, parent: 5, value: 'Pour water over coffee grounds' },
{ id: 7, parent: 5, value: 'Pour water over coffee grounds' }
];
function Tree() {
this.root = null;
// this function makes node root, if root is empty, otherwise delegate it to recursive function
this.add = function(node) {
if(this.root == null)
this.root = new Node(node);
else
// lets start our processing by considering root as parent
this.addChild(node, this.root);
}
this.addChild = function(node, parent) {
// if the provided parent is actual parent, add the node to its children
if(parent.id == node.parent) {
parent.children[node.id] = new Node(node);
} else if(parent.children[node.parent]) {
// if the provided parent children contains actual parent call addChild with that node
this.addChild(node, parent.children[node.parent])
} else if(Object.keys(parent.children).length > 0) {
// iterate over children and call addChild with each child to search for parent
for(let p in parent.children) {
this.addChild(node, parent.children[p]);
}
} else {
console.log('parent was not found');
}
}
}
function Node (node) {
this.id = node.id;
this.parent = node.parent;
this.value = node.value;
this.children = {};
}
const tree = new Tree();
// We are assuming that tasks are sorted in ascending order by parent
for(let t of tasks) {
tree.add(t);
}
console.log(JSON.stringify(tree.root))
Faites-moi savoir si vous avez des questions. Permet de le casser ensemble
Si votre entrée est déjà triée par identifiant et qu'aucun nœud enfant ne peut venir avant son nœud parent dans la liste, vous pouvez le faire en une seule boucle sans même avoir besoin de récursivité:
.as-console-wrapper{top:0;max-height:100%!important}
const tasks = [
{ id: 1, parent: null, value: 'Make breakfast' },
{ id: 2, parent: 1, value: 'Brew coffee' },
{ id: 3, parent: 2, value: 'Boil water' },
{ id: 4, parent: 2, value: 'Grind coffee beans' },
{ id: 5, parent: 2, value: 'Pour water over coffee grounds' }
];
const tasksById = Object.create(null);
// abusing filter to do the work of a forEach()
// while also filtering the tasks down to a list with `parent: null`
const root = tasks.filter((value) => {
const { id, parent } = value;
tasksById[id] = value;
if(parent == null) return true;
(tasksById[parent].children || (tasksById[parent].children = [])).push(value);
});
console.log("rootNodes", root);
console.log("tasksById", tasksById);
J'ai eu la même question lors d'une interview et je n'ai pas été en mesure de la résoudre. J'étais également confus que la fonction ne devrait prendre le tableau que comme premier et seul argument.
Mais après l'avoir retravaillé plus tard (et avec quelques très bonnes suggestions d'un homme brillant), j'ai réalisé que vous pouvez appeler la fonction avec le array comme premier et unique argument la première fois, puis pendant l'appel de récursivité en passant le parent comme second argument.
Dans la fonction, il vous suffit de vérifier si le deuxième argument n'est pas défini, si c'est le cas, vous recherchez dans le tableau votre objet racine et l'assignez à votre deuxième argument.
Voici donc ma solution, j'espère qu'elle sera plus claire:
function toTree(arr, item) {
if (!item) {
item = arr.find(item => item.parent === null)
}
let parent = {...item}
parent.children =
arr.filter(x => x.parent === item.id)
.sort((a, b) => a.id - b.id)
.map(y => toTree(arr, y))
return parent
}
toTree(tasks)
Le parent d'un nœud enfant sera-t-il toujours répertorié dans le tableau plat en premier, avant ledit nœud enfant?
duplication de stackoverflow com / questions / 18017869 /…