J'ai une arborescence de données avec des enfants:
{
id: 7,
name: "Cat",
parent_id: 1,
children: []
}
Tout objet de données enfant peut avoir plus d'enfants, comme indiqué dans les données ci-dessus. Cela représente une structure DOM dans laquelle un utilisateur peut sélectionner un élément pour y ajouter un enfant.
J'ai un titre de texte connu de l'élément sélectionné dans le DOM ainsi que les données que l'utilisateur souhaite insérer. J'ai du mal à trouver un algorithme récursif qui me permettra d'ajouter les nouvelles données au niveau correct de l'arbre.
Voici une liste de moi qui réfléchit au problème et essaie de le pseudo coder:
contributions:
les sorties:
pas:
Voici mon code:
function askUserForNewItem(e) {
const tree = getTree(); // returns above tree data structure
const name = prompt( 'Enter new item’s name:' ); // user input to match and insert as new item in tree
const clickedTitle = getClickedTitle(e); // returns string title of clicked on item from DOM - for example "Dog" or "Bowl"
const parent = determineParent(tree, clickedTitle);
const parent_id = parent[0].id;
// TODO - needs to set real unique id (highest unused id)
const newId = 101; // hard coded for now, needs to be dynamic
// TODO - needs to insert into correct level of children array in tree
return tree.children.push({ id: newId, name, emoji, children: [], parent_id: parent_id });
}
function determineParent(tree, clickedTitle) {
if(tree.children.length === 0) {
return false;
}
let treeLevel = tree;
let parent = [];
while(treeLevel.children.length !== 0) {
parent = treeLevel.children.filter(child => child.name === clickedTitle);
if(parent.length !== 0) {
break;
}
else {
// what to do here to make this recursive?
}
}
return parent;
}
Donc, si un utilisateur a tapé "Chat" en cliquant sur le bouton Ajouter pour "Chien", alors un nouvel objet
{ id: 1,
name: "Dog",
parent_id: null,
children: [
{
id: 2,
name: "Food",
parent_id: 1,
children: []
},
{
id: 3,
name: "Water",
parent_id: 1,
children: [
{
id: 4,
name: "Bowl",
parent_id: 3,
children: []
},
{
id: 5,
name: "Oxygen",
parent_id: 3,
children: []
},
{
id: 6,
name: "Hydrogen",
parent_id: 3,
children: []
}
]
}
]
}
Serait inséré dans les enfants de l'objet "Chien" de premier niveau dans l'arborescence de données.
3 Réponses :
Si vous voulez une solution récursive, vous devez modifier la méthode determineParent afin qu'elle recherche dans l'arborescence. Je ne suis pas sûr que ce soit exactement ce que vous recherchez, mais j'espère que vous avez l'idée générale
this.determineParent(tree,"title",100);
L'idée est de commencer au nœud le plus haut (curNode) et de déterminer d'abord si c'est le bon parent, sinon de prendre les premiers enfants pour voir si cela correspond et sinon de rechercher ses enfants et ainsi de suite.
Lorsque vous traitez avec la récursion, il peut être nécessaire de gérer la situation où vous pouvez rencontrer des références circulaires, considérez un scénario où un nœud a un enfant qui pointe vers les nœuds parent ou grand-parent, la méthode récursive fonctionnera pour toujours (dans la vraie vie, elle fonctionnera hors de l'espace de pile et lever une exception).
D'une part, il inclut un compteur de sauvegarde qui est diminué à chaque appel récursif, puis renfloué lorsqu'il atteint zéro.
function determineParent(curNode, clickedTitle, safeGuard) {
if(curNode.name===clickedTitle)
return curNode; // found the parent node with the correct clickedTitle
if(safeGuard===0)
return null; // bail out
// not found yet, do a recusive search down the tree.
for(const node of curNode.children) {
return determineParent(node,clickedTitle,--safeGuard);
}
return null; // not found.
}
puis appelez-le comme
function determineParent(curNode, clickedTitle) {
if(curNode.name===clickedTitle)
return curNode; // found the parent node with the correct clickedTitle
// not found yet, do a recusive search down the tree.
for(const node of curNode.children) {
return determineParent(node,clickedTitle);
}
return null; // not found.
}
pour limiter le nombre de recherches à 100.
Si vous pouvez utiliser Lodash + Deepdash , alors:
let child = {
name: "Cat",
children: []
};
let maxUsedId=-1;
_.eachDeep([data],(val)=>{
if(val.id>maxUsedId){
maxUsedId = val.id;
}
if(val.name==parentName){
val.children.push(child);
child.parent_id = val.id;
}
},{tree:true});
child.id=maxUsedId+1;
Pas un grand fan de réinventer la roue, surtout en ce qui concerne les algorithmes. Voici comment vous pouvez utiliser l' analyse d' objets pour résoudre votre problème. Nous l'utilisons pour le traitement des données car il est assez puissant une fois que vous en avez la tête
const objectScan = require('object-scan');
const insert = (tree, parentName, childName) => objectScan(['**.name'], {
abort: true,
rtn: 'bool',
filterFn: ({ value, parent }) => {
if (value === parentName) {
parent.children.push({
id: Math.max(...objectScan(['**.id'], { rtn: 'value' })(tree)) + 1,
name: childName,
parent_id: parent.id,
children: []
});
return true;
}
return false;
}
})(tree);
const data = {"id":1,"name":"Dog","parent_id":null,"children":[{"id":2,"name":"Food","parent_id":1,"children":[]},{"id":3,"name":"Water","parent_id":1,"children":[{"id":4,"name":"Bowl","parent_id":3,"children":[]},{"id":5,"name":"Oxygen","parent_id":3,"children":[]},{"id":6,"name":"Hydrogen","parent_id":3,"children":[]}]}]};
console.log(insert(data, 'Dog', 'Cat')); // true iff insert was successful
// => true
console.log(JSON.stringify(data));
// => {"id":1,"name":"Dog","parent_id":null,"children":[{"id":2,"name":"Food","parent_id":1,"children":[]},{"id":3,"name":"Water","parent_id":1,"children":[{"id":4,"name":"Bowl","parent_id":3,"children":[]},{"id":5,"name":"Oxygen","parent_id":3,"children":[]},{"id":6,"name":"Hydrogen","parent_id":3,"children":[]}]},{"id":7,"name":"Cat","parent_id":1,"children":[]}]}
Lors de la génération, vous pouvez directement attacher l'écouteur au bouton qui maintient le nœud souhaité à travers une fermeture, alors c'est aussi simple que
node.children.push({ /*...*/ })@JonasWilms Je n'ai pas la possibilité de modifier ou de modifier l'auditeur.