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

Je me base sur la réponse de @Ravindra, mais avec une vraie récursion.

function searchTree(element, matchingTitle){
     if(element.title == matchingTitle){
          return element;
     }else if (element.children != null){
          var i;
          var result = null;
          for(i=0; result == null && i < element.children.length; i++){
               result = searchTree(element.children[i], matchingTitle);
          }
          return result;
     }
     return null;
}

Alors vous pourriez l'appeler :

var element = data[0];
var result = searchTree(element, 'randomNode_1');

Answer 2

Voici une solution itérative :

var stack = [], node, ii;
stack.push(root);

while (stack.length > 0) {
    node = stack.pop();
    if (node.title == 'randomNode_1') {
        // Found it!
        return node;
    } else if (node.children && node.children.length) {
        for (ii = 0; ii < node.children.length; ii += 1) {
            stack.push(node.children[ii]);
        }
    }
}

// Didn't find it. Return null.
return null;

Answer 3

Voici une fonction itérative utilisant l'approche Stack, inspirée par La réponse de FishBasketGordo mais en profitant de certains ES2015 syntaxe pour raccourcir les choses.

Comme cette question a déjà été vue de nombreuses fois, j'ai décidé de mettre à jour ma réponse pour fournir également une fonction avec des arguments qui la rend plus flexible :

function search (tree, value, key = 'id', reverse = false) {
  const stack = [ tree[0] ]
  while (stack.length) {
    const node = stack[reverse ? 'pop' : 'shift']()
    if (node[key] === value) return node
    node.children && stack.push(...node.children)
  }
  return null
}

De cette façon, il est maintenant possible de passer les données tree elle-même, le value pour rechercher et aussi la propriété key qui peut avoir la valeur souhaitée :

search(data, 'randomNode_2', 'title')

Enfin, ma réponse originale utilisait Array.pop ce qui conduit à faire correspondre le dernier élément en cas de correspondances multiples. En fait, quelque chose qui pourrait être vraiment déroutant. Inspiré par Commentaire sur Superole je l'ai fait utiliser Array.shift maintenant, donc le premier entré, premier sorti est le comportement par défaut.

Si vous voulez vraiment l'ancien dernier entré, premier sorti j'ai fourni un arg supplémentaire reverse :

search(data, 'randomNode_2', 'title', true)

Answer 4

Ma réponse est inspirée de la réponse itérative de FishBasketGordo. C'est un peu plus complexe mais aussi beaucoup plus flexible et vous pouvez avoir plus qu'un seul noeud racine.

/**searchs through all arrays of the tree if the for a value from a property
 * @param aTree : the tree array
 * @param fCompair : This function will receive each node. It's upon you to define which 
                     condition is necessary for the match. It must return true if the condition is matched. Example:
                        function(oNode){ if(oNode["Name"] === "AA") return true; }
 * @param bGreedy? : us true to do not stop after the first match, default is false
 * @return an array with references to the nodes for which fCompair was true; In case no node was found an empty array
 *         will be returned
*/
var _searchTree = function(aTree, fCompair, bGreedy){
    var aInnerTree = []; // will contain the inner children
    var oNode; // always the current node
    var aReturnNodes = []; // the nodes array which will returned

    // 1. loop through all root nodes so we don't touch the tree structure
    for(keysTree in aTree) {
        aInnerTree.push(aTree[keysTree]);
    }
    while(aInnerTree.length > 0) {
        oNode = aInnerTree.pop();
        // check current node
        if( fCompair(oNode) ){
            aReturnNodes.push(oNode);
            if(!bGreedy){
                return aReturnNodes;
            }
        } else { // if (node.children && node.children.length) {
            // find other objects, 1. check all properties of the node if they are arrays
            for(keysNode in oNode){
                // true if the property is an array
                if(oNode[keysNode] instanceof Array){
                    // 2. push all array object to aInnerTree to search in those later
                    for (var i = 0; i < oNode[keysNode].length; i++) {
                        aInnerTree.push(oNode[keysNode][i]);
                    }
                }
            }
        }
    }
    return aReturnNodes; // someone was greedy
}

Enfin, vous pouvez utiliser la fonction comme ceci :

var foundNodes = _searchTree(data, function(oNode){ if(oNode["title"] === "randomNode_3") return true; }, false);
console.log("Node with title found: ");
console.log(foundNodes[0]);

Et si vous voulez trouver tous les noeuds avec ce titre, vous pouvez simplement changer le paramètre bGreedy :

var foundNodes = _searchTree(data, function(oNode){ if(oNode["title"] === "randomNode_3") return true; }, true);
console.log("NodeS with title found: ");
console.log(foundNodes);

Answer 5

Vous devez utiliser la récursion.

var currChild = data[0];
function searchTree(currChild, searchString){
     if(currChild.title == searchString){
          return currChild;
     }else if (currChild.children != null){
          for(i=0; i < currChild.children.length; i ++){
               if (currChild.children[i].title ==searchString){
                    return currChild.children[i];
               }else{
                    searchTree(currChild.children[i], searchString);
               }
          }
          return null;
     }
     return null;
}