Cómo encontrar un nodo en un árbol con JavaScript

Question

Tengo y objeto literal que es esencialmente un árbol que no tiene un número fijo de niveles. ¿Cómo puedo hacer una búsqueda en el árbol de un nodo en particular y luego devolver ese nodo cuando se encuentra de manera efciente en javascript?

Esencialmente tengo un árbol como este y me gustaría encontrar el nodo con el título '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

Basando esta respuesta en la respuesta de @ Ravindra, pero con verdadera recursividad.

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

Entonces se podría llamar:

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

Answer 2

Este es un problema básico de la recursividad.

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

    return returnData; 
} 

Answer 3

Debes usar recursion.

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

Answer 4

Aquí es una solución iterativa:

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

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

Answer 5

La siguiente está trabajando en mi extremo:

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 6

Mi respuesta está inspirada en la respuesta iterativa de FishBasketGordo. Es un poco más complejo pero también mucho más flexible y puede tener más de un nodo raíz.

/**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 
} 

Finalmente, puede utilizar la función como esta:

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

Y si usted quiere encontrar todos los nodos con este título sólo tiene que cambiar el parámetro 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 7

Este la función es universal y busca de forma recursiva. No importa, si el árbol de entrada es un objeto (raíz única) o una matriz de objetos (muchos objetos raíz). Puede configurar el nombre de utilería que contiene la matriz de elementos secundarios en objetos de árbol.

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

he comprobado necesitas cigarros y funciona bien, pero de alguna manera no se ejecutará en jsFiddle o jsbin ... (temas recurency en esos sitios ??)

código

de ejecución:

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); 

funciona en http://www.pythontutor.com/live.html#mode=edit (pegar el código)

Answer 8

Una solución recursiva flexible que funcionará para cualquier árbol

// 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); 
    }