J'ai une structure d'arbre de données avec des enfants:

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

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 auquel 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 bon niveau de l'arbre.

Voici une liste de moi réfléchissant au problème et essayant de le pseudo-coder :

Contributions:

  1. arbre (données ci-dessus)
  2. parentTitle de l'élément cliqué dans le DOM

Les sorties:

  1. arbre avec élément inséré

Pas:

  1. déterminer l'identifiant le plus utilisé pour savoir quel est le prochain identifiant unique
  2. vérifier le niveau actuel des données pour la correspondance avec le titre du parent
  3. s'il correspond, définissez id et parent_id dans les nouvelles données et transférez-les dans les enfants du parent
  4. si aucune correspondance, vérifiez si les données de niveau actuel ont des enfants
  5. si le niveau actuel a des enfants, il faut répéter les étapes 2+ pour chacun jusqu'à ce qu'une correspondance soit trouvée

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é « Cat » en cliquant sur le bouton d'ajout pour « Chien », alors un nouvel objet

{
    id: 7,
    name: "Cat",
    parent_id: 1,
    children: []
}

Serait inséré dans les enfants de l'objet "Chien" de premier niveau dans l'arbre de données.

2
DrCord 9 mars 2019 à 20:46

3 réponses

Meilleure réponse

Si vous souhaitez une solution récursive, vous devez modifier la méthode determineParent afin qu'elle effectue une 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 une idée générale

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.
}

L'idée est de commencer au nœud le plus haut (curNode) et de déterminer d'abord s'il s'agit du bon parent, sinon, prenez les premiers enfants pour voir s'il correspond et sinon, recherchez vers le bas, ce sont les enfants et ainsi de suite.

Lorsqu'il s'agit de récursivité, il peut être nécessaire de gérer la situation dans laquelle vous pouvez rencontrer des références circulaires, envisagez un scénario dans lequel un nœud a un enfant qui pointe vers le parent ou le grand-parent du nœud, la méthode récursive s'exécutera pour toujours (dans la vraie vie, elle s'exécutera hors de l'espace de la pile et lève une exception).

Dans un sens, cela 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 l'appeler comme

  this.determineParent(tree,"title",100);

Pour limiter le nombre de recherches à 100.

1
MikNiller 10 mars 2019 à 09:40

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;

Codepen pour ça

0
Yuri Gor 11 mars 2019 à 21:04

Pas un grand fan de réinventer la roue, surtout quand il s'agit d'algorithmes. Voici comment vous pouvez utiliser object-scan pour résoudre votre problème. Nous l'utilisons pour le traitement des données car il est assez puissant une fois qu'on a la tête autour de lui

// 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(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: [] } ] }
.as-console-wrapper {max-height: 100% !important; top: 0}
<script src="https://bundle.run/object-scan@13.7.1"></script>

Clause de non-responsabilité : je suis l'auteur de object-scan

0
vincent 9 janv. 2021 à 04:10