如何使用JavaScript在树中查找节点

Question

我有和object literal本质上是一个没有固定数量级别的树.我怎样才能在树中搜索特定节点,然后在javascript中以高效的方式返回该节点？

基本上我有一个像这样的树,并希望找到标题为'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

基于@Ravindra的回答得出这个答案,但是真正的递归.

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

然后你可以称之为:

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

Answer 2

这是一个迭代解决方案:

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

这是一个使用Stack方法的迭代函数，其灵感来自FishBasketGordo的答案，但它利用了某些ES2015语法来缩短内容。它还允许选择从其开始搜索的父节点。

function search (title, parent) {
  const stack = [ parent ]
  while (stack.length) {
    const node = stack.pop()
    if (node.title === title) return node
    node.children && stack.push(...node.children)
  }
  return stack.pop() || null
}

您可以这样简单地使用它：

let result = search('randomNode_1', data[0])

Answer 4

查找树中的节点：

假设我们有一棵树

let tree = [{
  id: 1,
  name: 'parent',
  children: [
    {
      id: 2,
      name: 'child_1'
    },
    {
      id: 3,
      name: 'child_2',
      children: [
        {
          id: '4',
          name: 'child_2_1',
          children: []
        },
        {
          id: '5',
          name: 'child_2_2',
          children: []
        }
      ]
    }
  ]
}];


function findNodeById(tree, id) {

   let result = null
   if (tree.id === id) {
        return tree;
   }

   if (Array.isArray(tree.children) && tree.children.length > 0) {
      tree.children.some((node) => {
        result = findNodeById(node, id);
        return result;
      });
   }
   return result;}

Answer 5

我的答案灵感来自FishBasketGordo的iterativ答案。它有点复杂，但也要灵活得多，您可以拥有多个根节点。

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

最后，您可以使用如下功能：

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

而且，如果您想查找所有具有此标题的节点，则只需切换bGreedy参数即可：

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