如何用JavaScript在樹中找到一個節點

Question

我有和對象字面值，它本質上是一個沒有固定數量級別的樹。我該如何去搜索樹中的某個特定節點，然後在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

這是基本的遞歸問題的節點。

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

    return returnData; 
} 

Answer 3

您必須使用遞歸。

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

下面是一個迭代的解決方案：

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

下在我結束工作：

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

我的答案受到FishBasketGordo迭代答案的啓發。這有點複雜，但也更加靈活，你可以有不止一個根節點。

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

Answer 7

這函數是通用的，並且遞歸地進行搜索。 如果輸入樹是對象（單根）或對象數組（很多根對象），則無關緊要。您可以配置在樹對象中保存children數組的prop名稱。

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

我localy測試，它工作正常，但它在某種程度上不會（在這些網站？recurency問題）

運行代碼上的jsfiddle或jsbin運行...：

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

它工作在http://www.pythontutor.com/live.html#mode=edit（粘貼代碼）

Answer 8

靈活的遞歸解決方案，適用於任何樹

工作

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