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

Cette fonction est universelle et effectue une recherche récursive. Peu importe si l'arbre d'entrée est un objet (racine unique) ou un tableau d'objets (plusieurs objets racine). Vous pouvez configurer le nom du prop qui contient le tableau des enfants dans les objets de l'arbre.

// Searches items tree for object with specified prop with value
// 
// @param {object} tree nodes tree with children items in nodesProp[] table, with one (object) or many (array of objects) roots
// @param {string} propNodes name of prop that holds child nodes array
// @param {string} prop name of searched node's prop
// @param {mixed} value value of searched node's  prop
// @returns {object/null} returns first object that match supplied arguments (prop: value) or null if no matching object was found

function searchTree(tree, nodesProp, prop, value) {
  var i, f = null; // iterator, found node
  if (Array.isArray(tree)) { // if entry object is array objects, check each object
    for (i = 0; i < tree.length; i++) {
      f = searchTree(tree[i], nodesProp, prop, value);
      if (f) { // if found matching object, return it.
        return f;
      }
    }
  } else if (typeof tree === 'object') { // standard tree node (one root)
    if (tree[prop] !== undefined && tree[prop] === value) {
      return tree; // found matching node
    }
  }
  if (tree[nodesProp] !== undefined && tree[nodesProp].length > 0) { // if this is not maching node, search nodes, children (if prop exist and it is not empty)
    return searchTree(tree[nodesProp], nodesProp, prop, value);
  } else {
    return null; // node does not match and it neither have children
  }
}

Je l'ai testé en local et il fonctionne bien, mais il ne fonctionne pas sur jsfiddle ou jsbin... (problèmes de récurrence sur ces sites ? ?).

code d'exécution :

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

    var r = searchTree(data, 'children', 'title', 'randomNode_1');
    //var r = searchTree(data, 'children', 'title', 'node2');  // check it too
    console.log(r);

Il fonctionne en http://www.pythontutor.com/live.html#mode=edit (coller le code)

Answer 2

C'est un problème de récursion de base.

window.parser = function(searchParam, data) {
  if(data.title != searchParam) {
    returnData = window.parser(searchParam, children)
  } else {
     returnData = data;
  }

  return returnData;
}

Answer 3

ES6+ :

const deepSearch = (data, value, key = 'title', sub = 'children', tempObj = {}) => {
    if (value && data) {
        data.find((node) => {
            if (node[key] == value) {
                tempObj.found = node;
                return node;
            }
            return deepSearch(node[sub], value, key, sub, tempObj);
        });
        if (tempObj.found) {
            return tempObj.found;
        }
    }
    return false;
};

const result = deepSearch(data, 'randomNode_1', 'title', 'children');

Answer 4

Ce qui suit fonctionne de mon côté :

function searchTree(data, value) {
if(data.title == value) {
    return data;
}
if(data.children && data.children.length > 0) {
    for(var i=0; i < data.children.length; i++) {
        var node = traverseChildren(data.children[i], value);
        if(node != null) {
            return node;
        }
    }
}
return null;

}

Answer 5

Une solution récursive flexible qui fonctionnera pour n'importe quel arbre

// predicate: (item) => boolean
// getChildren: (item) => treeNode[]
searchTree(predicate, getChildren, treeNode) {
        function search(treeNode) {
            if (!treeNode) {
                return undefined;
            }

            for (let treeItem of treeNode) {
                if (predicate(treeItem)) {
                    return treeItem;
                }

                const foundItem = search(getChildren(treeItem));

                if (foundItem) {
                    return foundItem;
                }
            }
        }

        return search(treeNode);
    }