Comment trouver un nœud dans un arbre avec JavaScript

Question

J'ai un objet littéral qui est essentiellement un arbre qui n'a pas un nombre fixe de niveaux. Comment puis-je rechercher un nœud particulier dans l'arbre et renvoyer ce nœud lorsqu'il est trouvé de manière efficace en javascript ?

Essentiellement, j'ai un arbre comme celui-ci et je voudrais trouver le nœud avec le titre 'randomNode_1'.

var data = [
{
title: 'topNode',
 children: [
   {
       title: 'node1',
       children: [
       {
           title: 'randomNode_1'
       },
       {   
           title: 'node2',
           children: [
           {
               title: 'randomNode_2',
               children:[
               {   
                   title: 'node2',
                   children: [
                   {
                       title: 'randomNode_3',
                   }]
               }
               ]
           }]
       }]
   }
  ]
 }];

Answer 1

Trouver tous les parents de l'élément dans l'arbre

let objects = [{
      id: 'A',
      name: 'ObjA',
      children: [
        {
          id: 'A1',
          name: 'ObjA1'
        },
        {
          id: 'A2',
          name: 'objA2',
          children: [
            {
              id: 'A2-1',
              name: 'objA2-1'
            },
            {
              id: 'A2-2',
              name: 'objA2-2'
            }
          ]
        }
      ]
    },
    {
      id: 'B',
      name: 'ObjB',
      children: [
        {
          id: 'B1',
          name: 'ObjB1'
        }
      ]
    }
    ];

let docs = [
  {

    object: {
      id: 'A',
      name: 'docA'
    },
    typedoc: {
      id: 'TD1',
      name: 'Typde Doc1'
    }
  },
  {

    object: {
      id: 'A',
      name: 'docA'
    },
    typedoc: {
      id: 'TD2',
      name: 'Typde Doc2'
    }
  },
  {

    object: {
      id: 'A1',
      name: 'docA1'
    },
    typedoc: {
      id: 'TDx1',
      name: 'Typde Doc x1'
    }
  },
  {

    object: {
      id: 'A1',
      name: 'docA1'
    },
    typedoc: {
      id: 'TDx2',
      name: 'Typde Doc x1'
    }
  },
  {

    object: {
      id: 'A2',
      name: 'docA2'
    },
    typedoc: {
      id: 'TDx2',
      name: 'Type de Doc x2'
    }
  },
  {

    object: {
      id: 'A2-1',
      name: 'docA2-1'
    },
    typedoc: {
      id: 'TDx2-1',
      name: 'Type de Docx2-1'
    },
  },
  {

    object: {
      id: 'A2-2',
      name: 'docA2-2'
    },
    typedoc: {
      id: 'TDx2-2',
      name: 'Type de Docx2-2'
    },
  },
  {

    object: {
      id: 'B',
      name: 'docB'
    },
    typedoc: {
      id: 'TD1',
      name: 'Typde Doc1'
    }
  },
  {

    object: {
      id: 'B1',
      name: 'docB1'
    },
    typedoc: {
      id: 'TDx1',
      name: 'Typde Doc x1'
    }

  }
];

function buildAllParents(doc, objects) {
    for (let o = 0; o < objects.length; o++) {
      let allParents = [];
      let getAllParents = (o, eleFinded) => {
        if (o.id === doc.object.id) {
          doc.allParents = allParents;
          eleFinded = true;
          return { doc, eleFinded };
        }
        if (o.children) {
          allParents.push(o.id);
          for (let c = 0; c < o.children.length; c++) {
            let { eleFinded, doc } = getAllParents(o.children[c], eleFinded);
            if (eleFinded) {
              return { eleFinded, doc };
            } else {
              continue;
            }
          }

        }
        return { eleFinded };
      };
      if (objects[o].id === doc.object.id) {
        doc.allParents = [objects[o].id];
        return doc;
      } else if (objects[o].children) {
        allParents.push(objects[o].id);
        for (let c = 0; c < objects[o].children.length; c++) {
          let eleFinded = null;`enter code here`
          let res = getAllParents(objects[o].children[c], eleFinded);
          if (res.eleFinded) {
            return res.doc;
          } else {
            continue;
          }
        }
      }

    }
  }

docs = docs.map(d => buildAllParents(d, objects`enter code here`))

Answer 2

Voici une option plus complexe - elle trouve le premier élément d'un nœud arborescent en fournissant (node, nodeChildrenKey, paires clé/valeur & paires clé/valeur supplémentaires facultatives)

const findInTree = (node, childrenKey, key, value,  additionalKey?, additionalValue?) => {
  let found = null;
  if (additionalKey && additionalValue) {
    found = node[childrenKey].find(x => x[key] === value && x[additionalKey] === additionalValue);
  } else {
    found = node[childrenKey].find(x => x[key] === value);
  }
  if (typeof(found) === 'undefined') {
    for (const item of node[childrenKey]) {
      if (typeof(found) === 'undefined' && item[childrenKey] && item[childrenKey].length > 0) {
        found = findInTree(item, childrenKey, key, value, additionalKey, additionalValue);
      }
    }
  }
  return found;
};

export { findInTree };

J'espère que cela aidera quelqu'un.

Answer 3

Il s'agit d'une recherche itérative de type "breadth first". Elle retourne le premier noeud qui contient un enfant d'un nom donné (nodeName) et d'une valeur donnée (nodeValue).

getParentNode(nodeName, nodeValue, rootNode) {
    const queue= [ rootNode ]
    while (queue.length) {
        const node = queue.shift()
        if (node[nodeName] === nodeValue) {
            return node
        } else if (node instanceof Object) {
            const children = Object.values(node)
            if (children.length) {
                queue.push(...children)
            }
        }
    }
    return null
}

Il serait utilisé comme ça pour résoudre la question initiale :

getParentNode('title', 'randomNode_1', data[0])

Answer 4

Amélioration du code basé sur " Erick Petrucelli "

1. Supprimer l'option "inverser".
2. Ajout du support multi-Root
3. Ajout d'une option permettant de contrôler la visibilité des "enfants".
4. Typescript prêt

5. Test unitaire prêt

   function searchTree( tree: Record<string, any>[], value: unknown, key = 'value', withChildren = false, ) { let result = null; if (!Array.isArray(tree)) return result;

   for (let index = 0; index < tree.length; index += 1) { const stack = [tree[index]]; while (stack.length) { const node = stack.shift()!; if (node[key] === value) { result = node; break; } if (node.children) { stack.push(...node.children); } } if (result) break; } if (withChildren !== true) { delete result?.children; }

   return result; }

Et les tests peuvent être trouvés à l'adresse suivante : https://gist.github.com/aspirantzhang/a369aba7f84f26d57818ddef7d108682

Answer 5

Version sans BS :

const find = (root, title) => 
  root.title === title ?
    root :
    root.children?.reduce((result, n) => result || find(n, title), undefined)